# Determine whether a number is prime

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?

-
If you down vote my question please let me know why so that I can improve my question asking in the future. –  KronoS Sep 24 '10 at 15:55
I had accidentally down-voted the question it appears... fixed now –  jericson Sep 28 '10 at 23:41
@jericson no prob just wanted to make the question better. –  KronoS Sep 29 '10 at 0:16
possible duplicate of How do you determine if a number is prime or composite? –  mixedmath Sep 5 '11 at 3:01
@mixedmath: what is your rationale for voting to close this qustion instead of the one you link to? –  t.b. Sep 7 '11 at 16:51

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.

-
Nice answer. Very informative! –  jericson Sep 23 '10 at 5:43
This is definitely the best answer overall. –  KronoS Sep 24 '10 at 2:43
@Charles you said "divide by 2, 3, 5, and so on until the square root of the number." Why is it sufficient to do check upto the square root of the number and why divide by only primes ? –  Geek Aug 14 '12 at 4:59
A composite number is always divisible by a prime number <= its square root. You can think of it this way: if you find a composite proper factor, either that has a prime factor <= its square root (which will divide the original number) or it has a composite factor <= its square root (in which case iterate). It can't have factors onlly larger than its square root since you could take one and divide the number by it to find one smaller than the square root. The process of taking smaller and smaller composite factors can't continue forever since there can be at most n steps. –  Charles Aug 14 '12 at 12:15

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?

-
Of course, once you check 2 you don't need to check any multiples of 2, and the same for 3 etc. But if you just want a simple algorithm and space/time constraints aren't an issue then what I wrote above would be very easy to program and would be fine for not too huge inputs. –  jericson Sep 23 '10 at 5:42
This is exactly what I was looking for. Not doing any crazy large numbers. –  KronoS Sep 24 '10 at 2:42
You don't need to check the following integer if $\sqrt{n}$ is not integral, you can stop just before it. If you store a list of primes, just divide by those up to $\sqrt{n}$ –  Ross Millikan Sep 5 '11 at 3:52
@RossMillikan: I think this is a guard against rounding errors. If you compute $\sqrt{p^2}$ as a little bit less than $p$ due to round-off you would mischaracterize $p^2$ as composite, but not if you checked to the next integer. –  Charles Apr 8 '13 at 15:28

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.

-

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.

-

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.

-
Calling the Miller-Rabin algorithm a “nondeterministic algorithm” is technically correct but misleading (in the same way as calling a rectangle a parallelogram). It is a randomized algorithm. –  Tsuyoshi Ito Sep 23 '10 at 12:36
@Tsuyoshi Ito: Changed. Thanks! :) –  Pratik Deoghare Sep 23 '10 at 12:53
It's worth mentioning that the efficient versions of AKS are no longer deterministic. –  Charles Sep 27 '10 at 14:54
@Sri: That's actually the funny thing about AKS; thus, it remains more a curiosity than a practical test. –  Ｊ. Ｍ. Sep 5 '11 at 2:57
@Srivatsan Narayanan: Glad to help. It's exciting times we're seeing! When the test first came out it was hard to imagine an efficient version, but thanks to improvements on the exponent (starting from the work of Berrizbeitia) and amazing millionfold improvements to the constant factor (due to Bernstein) the algorithm looks usable if not yet competitive. –  Charles Sep 5 '11 at 3:56

Construct a list of primes up to the maximum input $n$. (Construct using prime sieves.) Then, trial division for every such prime $\le \sqrt{n}$. This should work.

-
If you have constructed a list of primes up to your number, can you not just check to see if your number is in the list? –  user1729 May 6 '14 at 11:06
A better way might be to generate the sieve as you go, and check only up to the square root of n. I have no clue how efficient this is though... I imagine one of the above answers is better for a quick result. –  Alfred Yerger May 22 '14 at 6:56

## protected by Community♦May 3 '14 at 21:16

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.