Finding prime number

[aakashjohari]

tell me the algorithm of finding that a given number is whether prime or not.
i know a method -
as input is - 7
then i will execute a loop from 2 to sqrt(7) and i will check the divisibility.
but i want an algo faster than it or fastest.

[firedraco]

That is the only way, if there was a faster way, many cryptography programs would be really easy to break (like RSA).

[jsmith]

If the number you are looking for is relatively small, then you can also use the sieve of eratosthenes.

Otherwise, there are some small optimizations you can make to the algorithm.
Check for division by 2, 3, 5, and 7. If none are factors, then you only
need to check subsequent numbers that end in 1, 3, 7, or 9 (eg, 11, 13, 17, 19,
21, 23, 27, 29).

So I'd do something like this:

//pseudo-code
if( num is divisble by 2, 3, 5, or 7 )
    output "not prime";
    exit;

unsigned long root = static_cast<unsigned long>( sqrt( num ) );
for( unsigned long base = [10...root] counting by 10 )
   if( num is divisible by base + 1 OR
      num is divisible by base + 3 OR
      num is divisible by base + 7 OR
      num is divisible by base +9 )
      output "not prime"
      exit;
end for