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?
Determine whether a number is prime
-
0@Theo: ah, you mention this and I see something I hadn't noticed. I assumed this question was newer because Charles edited it only recently - I failed to note that the original question is very old, older than the one I linked to. But in general, I close the new in favor of the old. I'm sorry about that here - good catch. – 2011-09-07
6 Answers
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.
-
0A 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. – 2012-08-14
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?
-
0@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. – 2013-04-08
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.
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.
-
1@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. – 2011-09-05
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.
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.
-
0if you already have constructed a list of primes upto your number then why can't you just check if the number entered is prime :P – 2015-11-18