Algorithm for prime number

[Karlwakim]

Hi everybody,
How can i find out if a number is prime or not ?
For example :

#include <iostream>
using namespace std;
int main () {
int number;
bool isprime;
cin >> number;
/*algorithm
..............
..............
..............
*/
if (isprime == false) {
cout << "Not prime";
} else {
cout << "Prime";
}


}

[frogboy77]

So if isprime equals true then the output is "Not prime"?

[Karlwakim]

Thanks frogboy77, i corrected it

[DeanMSands3]

Let's start with the basic psuedo code:

X=2
WHILE X IS LESS THAN MY_NUMBER
IF MY_NUMBER MODULO X IS 0
THEN RETURN FALSE
ELSE INCREMENT X BY 1
LOOP
RETURN TRUE

Now, that's fantastic and all, but it's very inefficient.
After 2, there aren't anymore even primes. Let's make our code look like this:

IF MY_NUMBER MODULO 2 EQUALS 0
THEN RETURN FALSE
X=3
WHILE X IS LESS THAN MY_NUMBER
IF MY_NUMBER MODULO X IS 0
THEN RETURN FALSE
ELSE INCREMENT X BY 2
LOOP
RETURN TRUE

Since a prime number is any number where N=/=X*Y where X and Y are positive integers other than 1, it stands reason that there's going to be some overlap.
Let's have a look at the factors of 12, not counting 1.

12/2=6
12/3=4
12/4=3
12/6=2

Doesn't that look funny?
Why are we checking 4 and 6 when we've already check 3 and 2. Where to draw the line? At the square root of course. However, a square root operation is expensive when added to the loop. But a simple multiply isn't so bad.

IF MY_NUMBER MODULO 2 EQUALS 0
THEN RETURN FALSE
X=3
WHILE X*X IS LESS THAN MY_NUMBER
IF MY_NUMBER MODULO X IS 0
THEN RETURN FALSE
ELSE INCREMENT X BY 2
LOOP
RETURN TRUE

Now, if you really want to have some fun and you're going to be checking a lot of numbers you do it a little different.
Instead of incrementing X by 2, you just point it to the next prime number in a list. And if you run to the end of the list, keep finding new primes and add them to the list.

Happy coding!

[jaskij]

There are many algorithms.

Unless your numbers are ridiculously large, I suggest using Eratosthenes' sieve and then checking up to the square root of the number (for every divisor of a number under it's square root there is a corresponding one above it).

Or you could just hard-code a list of primes and then check against it. There are many lists of primes on the net, google it.

@DeanMSands3: even better then using squaring, you could just precompute the square root.