Prime or Not

[kosilva]

I trying to create a program that tells you when a number (integer) is a prime number or not


int integer, x;
bool isPrime = true;

while (true)
{
cout << "\nGive me an integer: ";
cin >> integer; cin.ignore(80,'\n');

for ( x = 2; x < integer; ++x )
(integer%x == 0 ? isPrime = true : isPrime = false);
cout << integer << ( (x - 1) == integer ? " is " : " is NOT ") << "a prime number\n";
}

[OxBADC0DE]

Here's a simple algorithm for finding a prime number, preferably using a bool function:

1. A boolean variable initialized as true.
2. A for loop variable(x) that starts from 2 to n-1(where n==number being tested) and x is incremented after testing.
3. If n%x is found to be 0 then the bool variable before the for loop turns to false and the loop breaks immediately, therefore return false.
4. Else if none of the values of x divides it, return true.

true for primeness and false for non-prime numbers.

[kosilva]

but I have to do something either on my condition inside the for loop, or on my conditional operator because right now for every integer I enter is saying that it is prime.

[Chervil]

This line doesn't give the correct result:
(integer%x == 0 ? isPrime = true : isPrime = false);

Expanded, that line looks like this:

    if (integer%x == 0)
    {
        isPrime = true;
    }
    else 
    {
        isPrime = false;
    }

But that code is incorrect. If this is true, integer%x == 0 then we know for sure that the number is not prime. But if it's false we don't immediately conclude that it is prime.

We can only do this:

    if (integer%x == 0)
    {
        isPrime = false;
    }

If that code is inside a loop, add the break keyword too, as there's no need to continue with the rest of the loop.

[moorecm]

Note that this algorithm will not scale very well... If you need better performance you should do a little more research on the subject. (It's good for you to search around and think about the problem on your own.)

[ResidentBiscuit]

Look into a sieve. They're not particularly difficult to implement, and much more efficient than this.

[Chervil]

I'd say choose an appropriate tool depending on the job to be done. Just as paintbrushes come in different sizes (as well as other methods of applying paint), the choice of algorithm depends on the task at hand.

[kosilva]

thanks for the help!!! i did i just had the condition in the for loop wrong!!! i change x < integer to x < sqrt((double)integer)

[Chervil]

change x < integer to x < sqrt((double)integer)

I think that should be x <= sqrt((double)integer) otherwise 4 and 9 will be considered prime.

However, some care is needed. The reason for doing this is to make the code more efficient. But if that condition is placed in the for () statement, it means the square root function is called on every iteration of the loop, which is adding unnecessary overhead. Preferably do the calculation just once, before the loop starts, and assign the result to a variable.

[kosilva]

oh ok!!! thanks for the tips Chervil!!! ;)