[C++] IsPrime(int x)

Discussion in 'General Programming Support' started by tooltiperror, Apr 22, 2010.

  1. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    I've been writing a function in C++ to see if something is prime. My first thought process was that you could check to see if something is composite by seeing if it was divisible by a number in a loop, and exit when the integer reaches the integer x, the argument. The problem is, I can't find out how to check if something is a whole number.


    This is what I have so far (I am aware it's incomplete):
    Code:
    {
    	int y;
    	for (y=1; NULL; y++) {
    		if (x=1) {
    			//It is composite,
    			return 1; // so return 1.
    		}
    	} // If it isn't composite, it
    	return 0; // must be prime.
    }
    
     
  2. Slapshot136

    Slapshot136 Divide et impera

    Ratings:
    +483 / 2 / -0
    look into the mod operator (%) - it returns the "remainder" - if the remainder is 0, then it divides nicely

    also, you only need to check up the the square root of the number, because lets say the number you are checking is 14 - you will notice that "2" and "7" both divide into it, but they are a pair (one above the square-root mark, and one below the square-root mark, or both are the exact square root if it's a perfect square) - you can stop once you find 2, and if you don't find any up to the square-root mark, then you know that there won't be any after that
     
  3. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    Oh, thanks, I think I know what to do now.

    Edit: Figured it out.

    Code:
     int main ()
    {
    	int input;
    	int x;
    	int y;
    	int cc;
    	cout<<"Please enter a number: ";
    	cin>>input;
    	if (input%2!=0 and input%3!=0) {
    		cout<<"Your number is prime.\n";
    		return 0;
    	}
    	cout<<"Your number is composite.\n";
    	return 0;
    }
    
     
  4. Slapshot136

    Slapshot136 Divide et impera

    Ratings:
    +483 / 2 / -0
    your test there only works for small numbers, it would mark 25 as prime for example
     
  5. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    That's because I would have to add in a loop for additional numbers through 9, right?
     
  6. Xienoph

    Xienoph You can change this now in User CP.

    Ratings:
    +43 / 0 / -0
    Why 9? I think you can do better than that ;)
     
  7. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    What number can not be divided from a number from 2-9 but it still composite?
     
  8. Slapshot136

    Slapshot136 Divide et impera

    Ratings:
    +483 / 2 / -0
    something like 11^2, or actually any prime number greater then 9 squared, or any 2 prime numbers greater then 9 multiplied
     
  9. monoVertex

    monoVertex I'm back!

    Ratings:
    +459 / 0 / -0
    Ideally, you are supposed to loop till x/2, to be sure ;). Like slapshot said, 121 is a number that is not divided by 2-9, but it still composites.
     
    • Like Like x 1
  10. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    The x/2 thing totally just gave me a huge idea.

    Will edit this post with a (I think) correct code.

    Edit:

    Now, for some reason, what I thought was correct, skips 5 as a prime number.

    Code:
     #include <iostream>
     #include <cstdlib>
      using namespace std;
    
    int isPrime(int x);
    
     int main ()
    {
    	int input;
    	int count;
    	int y;
    	cout<<"Please, enter a number: ";
    	cin>>input;
    	if (isPrime(input)==1) {
    		cout<<"Your number is already prime.\n";
    		return 0;
    	}
    	for (count=input; y!=1; count++) {
    		if (isPrime(count)==1) {
    			cout<<"The next prime number is "<<count<<".\n";
    			y=1;
    		}
    	}
    	cin.get();
    	return 0;
    }
    
      int isPrime(int x)
    {
    	//int z=x%2;
    	//int y=x%3;
    	//int w=x%5;
    	//if (z!=0 && y!=0 or x==3) {
    	//	return 1; //1=prime;
    	//}
    	
    	int y;
    	for (y=1; y < x/2; y++) {
    		if (x%y!=0) {
    			return 1;
    		}
    	}
    	return 0;
    }
    
     
  11. Xienoph

    Xienoph You can change this now in User CP.

    Ratings:
    +43 / 0 / -0
    Or better: square root of x.

    A further optimization would be to start with Miller Rabin Primality Test
     
  12. Darthfett

    Darthfett Super Mod

    Ratings:
    +613 / 0 / -0
    I would start the loop with 2, since all numbers are divisible by 1.

    I've never heard of, or seen that Miller-Rabin test, but it is quite confusing. :p
     
  13. Dave312

    Dave312 Censored for your safe viewing

    Ratings:
    +269 / 0 / -0
    You really only need to try and divide by prime numbers as well. However writing code to do that would be rather tricky. So instead you should check if the number is even (if it is then it is definitely not a prime unless the number is 2), then start looping from 3 and use a step of 2 so that you are only checking odd numbers. This would half the time it takes (useful for large numbers)
     
  14. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    Alright, now I'm really confused.

    My thought process was that if you can be divided evenly by anything greater than one and less than half of you, you're composite. But the problem is, my loop isn't working correctly, and I'm not sure why.

    Code:
      int isPrime(int x)//1==prime;
    {	
    	int y;
    	for (y=2; y==x/2; y++){
    		if (x%y==0) {
    			return 0;
    		}
    	}
    	return 1;
    }
    
     
  15. Xienoph

    Xienoph You can change this now in User CP.

    Ratings:
    +43 / 0 / -0
    Don't you want y <= x / 2? Not y == x/2?
     
  16. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    Works now, thanks. Will it work now forever?

    Code:
     #include <iostream>
     #include <cstdlib>
      using namespace std;
    
    int isPrime(int x);
    
     int main ()
    {
    	int input;
    	int count;
    	int y;
    	cout<<"Please, enter a number: ";
    	cin>>input;
    	if (isPrime(input)==1) {
    		cout<<"Your number is already prime.\n";
    		return 0;
    	}
    	for (count=input; y!=1; count++) {
    		if (isPrime(count)==1) {
    			cout<<"The next prime number is "<<count<<".\n";
    			y=1;
    		}
    	}
    	cin.get();
    	return 0;
    }
    
      int isPrime(int x)
    {	
    	int y;
    	for (y=2; y<=x/2; y++)
    	{
    		if (x%y==0) 
    		{
    			return 0;
    		}
    	}
    	return 1;
    }
    
     
  17. Xienoph

    Xienoph You can change this now in User CP.

    Ratings:
    +43 / 0 / -0
    I think it looks good. As I have said, an optimization would be to stop at square root of x. Why? Well, suppose a number n is a composite. Then n = a * b. But one of a or b must be less than square root of n (think about it for a second ... use calculus if you're still not convinced). So, it is sufficient to check everything from 1 to square root of n.
     
  18. Darthfett

    Darthfett Super Mod

    Ratings:
    +613 / 0 / -0
    n = a * b. If a is 1, b is automatically going to be equal to n. Use 2, as it is the next integer in the sequence 1 to n.
     
    • Like Like x 1
  19. Xienoph

    Xienoph You can change this now in User CP.

    Ratings:
    +43 / 0 / -0
    Yes, that's true. A further optimization, as suggested by Dave, would be to check for only odd numbers (after checking that n is not 2, of course)
     
    • Like Like x 1
  20. tooltiperror

    tooltiperror Super Moderator Staff Member

    Ratings:
    +233 / 0 / -0
    I'm a bit confused. How would I find the square root of the number?
     

Share This Page