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";
}

}``````

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

Thanks frogboy77, i corrected it

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!

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.