How do you write an algorithm to check whether a number is a prime number or not?

Answer 1

Checking if a number is prime is a popular question for programming competitions.

It's also necessary when implementing software that generates private keys for RSA public-key encryption.

There are several formulas for computing the prime numbers such as Willans' Formulas and Wormell's Formula. These two are used to generate a Prime number.

The simplest way to check if a given number is prime (primality testing) is to search for a factor.

Try possible factors and see if the number can be evenly divided into any of them.

In C, that simple check is:

bool IsPrime(long int number)

{

if (number < 2) return false;

if (number <= 3) return true;

long int ns, temp;

for (ns = 3; ns < number; ns++)

{

temp = number / ns;

if (temp*ns number) {

printf("The smallest prime factor of %li is %li .\n", number, ns );

printf("The product of %li * %li is %li .\n", ns, temp, number );

return false; //can be divided!

}

}

return true;

}

This can be sped up a little more by only checking primes (rather than every odd number), perhaps using the sieve of Eratosthenes to find those primes.

Because all primes are integers, it's usually best not to use floating-point when working with them.

Even with all known speedups, every known method for factorizing a number is still too slow for some applications -- it would take centuries to check the numbers used in RSA public-key encryption -- and so people have developed much faster, much more complicated algorithms for primality testing.

These fast algorithms can prove that a number is almost certainly prime; however, when they indicate that a number is composite, they don't reveal any of the factors of that composite number.

Such fast algorithms include

the Fermat primality test,

the cyclotomy test,

the Lucas test,

the Proth test.

the Miller-Rabin primality test,

the Solovay-Strassen primality test, and

the AKS primality test.

The implementation, of those formula, unfortunately cannot be listed in here.