Determine whether a number is prime

Question

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?

Answer 1

Have the program find the remainder when dividing the input (say n) by 2, 3, 4, ..., $\sqrt n$ (or the following integer if $\sqrt n$ is not an integer.) If this value ever leaves a remainder of zero then your number is composite and you can stop checking divisors. If the remainder is non-zero for all of these values then your number is prime.

There are more efficient ways to check primeness but this is probably the easiest way to program it and I imagine will suffice for your purposes. Unless you are checking very very large numbers?

Answer 2

How do I mathematically determine if a number is prime?

If the number is n, then dividing it by every prime number less than or equal to sqrt(n) and showing that there is a remainder.

There are a number of different sieve solutions for finding prime numbers, the oldest and most famous of which is the Sieve of Eratosthenes. These are generally easy to programme and can, for example, find all of the primes below 100,000 in a few milliseconds on a modern processor.

Answer 3

Algorithm posted by jericson is the best for basic purposes.

IMHO, for programming competitions and for practical purposes randomized algorithms are best. Rabin-Miller is my favorite.

Take a look at Rabin-Miller primality testing algorithm code @ TopCoder.

As primes are in P, there is deterministic, polynomial time algorithm called AKS primality test.

Answer 4

There are many different algorithms for primality testing. See the Wikipedia page for an introduction and see Henri Cohen's book "A course in computational algebraic number theory" for further details. See also Caldwell's Prime Pages.

Answer 5

For very small numbers (less than a million), trial division is the best way: divide by 2, 3, 5, and so on until the square root of the number. If you find a factor, the number is composite; otherwise, the number is prime.

For larger numbers there are better methods, but choosing which one depends on how much work you're willing to put into the program. It is now known that there are no BPSW-pseudoprimes below $2^{64}$, so if you can write that test (see here for details) then you have a very quick test for primality.

If you only need to test up to $2^{32}$, you can simply check if the number is a 2-strong pseudoprime. If so, test if it's one of 2314 exceptions (this can be done in 12 or 13 steps with a binary search); if the test fails or it's an exception, the number is composite, otherwise prime. (You can go higher than $2^{32}$ if you're willing to build an appropriate table of exceptions.)

For larger numbers, the work is usually split into two parts: determining with high probability (say, 99.99999999%) that the number is prime, then actually proving that it is. What type of proof depends on the form and size of the number.