Prime Number Check Calculator

Understanding the Prime Number Check Calculator

A prime checker tests whether a number has any divisor other than one and itself. Trial division answers it directly for small numbers and becomes hopeless quickly, which is why the primality tests used in practice do something entirely different.

How it actually works

Enter a whole number. The calculator tests divisibility by candidates up to the square root, since any factor above that pairs with one below. The value 97 is reported as prime.

The deeper context most people miss

If a number has a factor above its square root, the matching cofactor is below it, so a search that finds nothing below the square root has proved primality. That single observation reduces the work from n divisions to the square root of n, which is the difference between feasible and not for moderate numbers.

Why practical primality tests are probabilistic

Trial division is exact and scales badly: testing a 100-digit number would require more operations than there are atoms in the observable universe, so it is not merely slow but impossible. The tests actually used are probabilistic and rest on properties that primes satisfy and most composites do not. Fermat's little theorem states that for a prime p, any base raised to the power p minus one is congruent to one modulo p. A number failing that test is definitely composite. A number passing it is probably prime, with the qualification that Carmichael numbers pass for every base coprime to them and are composite, which makes the plain Fermat test unreliable. The Miller-Rabin test refines it by additionally examining square roots of one, and it has no analogue of Carmichael numbers: every composite fails for at least three quarters of possible bases, so repeating with random bases drives the error probability down geometrically, and forty rounds gives a failure chance far below the probability of a hardware error corrupting the answer. That is why cryptographic libraries use it despite it being probabilistic. A deterministic polynomial-time test exists, the AKS algorithm published in 2002, which settled a long-standing theoretical question and is too slow to displace Miller-Rabin in practice, which is a good illustration of theoretical and practical significance diverging.

A worked example: why 97 needs only four checks

Testing 97 requires trying divisors up to its square root, about 9.85, so only 2, 3, 5, and 7 need checking once even numbers and multiples of small primes are handled. That is four divisions rather than 96, and the saving grows: a million requires a thousand checks rather than a million. Restricting to prime divisors saves more, since any composite divisor has a prime factor already tested, and the wheel factorisation trick skips multiples of small primes entirely, checking only numbers of certain residues modulo 30 or 210. For finding all primes below a bound rather than testing one number, the sieve of Eratosthenes is far better than testing each individually: mark multiples of each prime as composite and whatever remains unmarked is prime, which finds every prime below a million in a fraction of a second. The sieve dates to the third century BC and remains the right approach for that problem. Its memory use grows with the bound, so segmented variants process ranges in blocks for very large limits. The distinction between testing one number and enumerating many is worth keeping, since the best algorithm differs completely between the two.

Deciding what primality actually gets used for

The dominant application is cryptography, where RSA key generation needs large primes, typically 1024 or 2048 bits each, found by generating random odd numbers of the right size and testing until one passes. The prime number theorem tells you how long that takes: primes near n have density roughly one in the natural logarithm of n, so among 2048-bit numbers about one in 1,400 is prime, and skipping even numbers and small multiples reduces the candidates to try substantially. That density result is what makes the whole approach viable. Beyond cryptography, primes appear in hash table sizing, where a prime modulus distributes keys more evenly when the hash function has weak bits, in pseudorandom generators where the modulus must satisfy conditions for full period, in error-correcting codes over prime fields, and in cicada life cycles, where 13 and 17 year periods are hypothesised to reduce synchronisation with predator cycles. The fundamental theorem of arithmetic, that every integer factors uniquely into primes, is what makes them the building blocks and is the reason so much of number theory reduces to statements about them. That factorisation is easy to verify and believed hard to compute is precisely the asymmetry RSA depends on.

What remains unknown about primes

Several questions that are simple to state remain open. The twin prime conjecture holds that infinitely many pairs of primes differ by two, and though it remains unproven, Yitang Zhang's 2013 result established that infinitely many prime pairs differ by at most 70 million, a bound subsequently reduced to 246 through collaborative work. Goldbach's conjecture, that every even number above two is the sum of two primes, has been verified computationally to enormous bounds and never proved. The Riemann hypothesis concerns the zeros of the zeta function and is equivalent to a precise statement about how regularly primes are distributed; it is among the most consequential open problems, with a great many results published conditionally on its truth. Against these, much is known. Euclid proved infinitely many primes exist, by a short argument showing that any finite list is incomplete. The prime number theorem describes their density asymptotically. Dirichlet proved that any arithmetic progression whose terms share no common factor contains infinitely many primes. The largest known primes are Mersenne primes, of the form two to a power minus one, found by distributed computing projects because a specially efficient test exists for that form. The gap between what is verified computationally and what is proved remains striking.

Variations: prime types and testing algorithms

Mersenne primes have the form two to a prime power minus one and admit the Lucas-Lehmer test, which is why the largest known primes take that shape. Fermat primes have the form two to a power of two plus one, with only five known. Twin primes differ by two, cousin primes by four, and sexy primes by six. Sophie Germain primes have the property that twice the prime plus one is also prime. Safe primes are used in cryptography for their structure. Pseudoprimes pass a probabilistic test while being composite, and Carmichael numbers pass the Fermat test for all coprime bases. For algorithms, trial division suits small numbers, the sieve of Eratosthenes suits enumerating a range, Miller-Rabin suits testing large candidates, Baillie-PSW combines tests with no known counterexample, and AKS is deterministic and impractically slow. For factorisation rather than testing, Pollard's rho suits small factors, the quadratic sieve and general number field sieve handle larger numbers, and Shor's algorithm would factor efficiently on a quantum computer of sufficient scale, which is why post-quantum cryptography is being standardised.

Testing for primality sensibly

Test divisors only up to the square root, since any factor above pairs with one below and finding none below proves primality. Restrict to prime divisors where you have them, since any composite divisor shares a prime factor already checked. Use the sieve of Eratosthenes when you need all primes below a bound rather than testing individual numbers, since the two problems have different best algorithms. Use Miller-Rabin for large numbers, since trial division is impossible beyond modest sizes and the probabilistic error can be driven below hardware failure rates. Avoid the plain Fermat test, since Carmichael numbers pass it for every coprime base while being composite. Expect prime density near n to be roughly one in the natural logarithm of n, which is what makes generating cryptographic primes by random search viable. Remember that one is not prime by definition, which keeps unique factorisation working. And note that testing primality is easy while factorising is believed hard, which is the asymmetry public key cryptography rests on.

What people get wrong

• Testing divisors all the way to n, when any factor above the square root pairs with one below and the search can stop there.
• Using trial division on large numbers, which is not merely slow but computationally impossible beyond modest sizes, where Miller-Rabin is the practical test.
• Relying on the Fermat test alone, since Carmichael numbers pass it for every coprime base while being composite, which Miller-Rabin has no analogue of.
• Treating one as prime, when excluding it is what keeps factorisation into primes unique and is a definition rather than an oversight.

Where the math comes from

A number is prime when it has no divisor other than one and itself. Trial division tests candidates up to √n, since any factor exceeding the square root pairs with a cofactor below it. This reduces the work from n operations to √n, which is decisive for moderate numbers and still infeasible for the large numbers used in cryptography.

Questions and answers

Related calculators

Arithmetic Series · Fibonacci · GCD and LCM · Modular Arithmetic · Sum of Powers