Secrets from Primes

Prime number checker

Type a whole number (up to 24 digits) or an expression such as 2^61 − 1. Every answer is exact.

The verdict, the prime factorization and how it was proved. Up to 1012 the checker divides by every candidate up to √n; above that it runs the strong (Miller–Rabin) test with the 13 prime bases 2 to 41, which is a proof for every number below 3.3 × 1024. Above 24 digits it refuses rather than guess.

How the checker decides

A prime number has exactly two divisors, 1 and itself. The checker gives a proof, not a guess, for every whole number up to 1024 − 1 (24 digits):

  • Up to 1012: trial division. If n is composite it has a divisor no larger than √n, because divisors come in pairs d × n/d and one of each pair is at most √n. The checker tries 2, 3 and every number of the form 6k ± 1 up to √n (at most one million)[1]. The table under the verdict shows the first of these divisions.
  • From 1012 to 1024 − 1: the strong test with 13 bases. After screening by the primes below 1000, the checker runs the strong (Miller–Rabin) test to the bases 2, 3, 5, …, 41[2][3]. A prime passes every base. Sorenson and Webster found the smallest odd composite that passes all 13 of these bases, ψ13 = 3,317,044,064,679,887,385,961,981 ≈ 3.3 × 1024[4][5]. Every number this checker accepts is below it, so passing all 13 bases proves primality.
  • Above 1024 − 1: refused. No fixed set of bases is known to be enough there, and a probabilistic answer (“probably prime”) is not what this page offers.

For a composite number, the checker also finds the prime factorization: trial division by every number up to 100,000, then Pollard's rho method for what remains[6][7], with a budget of four million steps. Every factor it reports has itself been proved prime. If the budget runs out, the leftover part is shown in brackets as a proved composite whose factors were not found; it is never called prime.

Worked examples

97. √97 ≈ 9.8, so try 2, 3, 5 and 7: the remainders are 1, 1, 2 and 6. None is 0, so 97 is prime.

91. It is odd, not a multiple of 3 (9 + 1 = 10), and does not end in 0 or 5, but 91 = 7 × 13. It is composite, and it is the smallest odd composite that many people take for a prime.

1. Neither prime nor composite. Counting it as a prime would break the uniqueness of prime factorizations (Prime numbers).

561. Composite (3 × 11 × 17), but it passes Fermat's test for every base that shares no factor with it: it is the smallest Carmichael number[8]. The strong test catches it at base 2.

267 − 1 = 147,573,952,589,676,412,927. A Mersenne number once thought prime; Frank Nelson Cole published its factors, 193,707,721 × 761,838,257,287, in 1903[9]. The checker finds them in milliseconds.

Prime or composite?

Every whole number above 1 is either prime or composite, never both. A composite number can be written as a product of two smaller whole numbers, such as 15 = 3 × 5; equivalently, it has a divisor other than 1 and itself. 0 and 1 are neither. Every composite number is a product of primes in exactly one way, apart from order: the fundamental theorem of arithmetic[1]. The checker's factorization is that product.

Sources

  1. Victor Shoup (2008). A Computational Introduction to Number Theory and Algebra, 2nd edition (Version 2, free PDF). Cambridge University Press. ISBN 9780521516440. textbook
  2. G. L. Miller (1976). Riemann's hypothesis and tests for primality. Journal of Computer and System Sciences 13 (3), 300–317. doi:10.1016/S0022-0000(76)80043-8. paper
  3. M. O. Rabin (1980). Probabilistic algorithm for testing primality. Journal of Number Theory 12 (1), 128–138. doi:10.1016/0022-314X(80)90084-0. paper
  4. J. P. Sorenson and J. Webster (2017). Strong pseudoprimes to twelve prime bases. Mathematics of Computation 86 (304), 985–1003. doi:10.1090/mcom/3134. paper
  5. The OEIS Foundation (2025). A014233: Smallest odd number for which the Miller–Rabin test with the first n prime bases fails (ψ_n). The On-Line Encyclopedia of Integer Sequences. database
  6. J. M. Pollard (1975). A Monte Carlo method for factorization. BIT Numerical Mathematics 15, 331–334. doi:10.1007/BF01933667. paper
  7. R. P. Brent (1980). An improved Monte Carlo factorization algorithm. BIT Numerical Mathematics 20, 176–184. doi:10.1007/BF01933190. paper
  8. The OEIS Foundation (2025). A002997: Carmichael numbers. The On-Line Encyclopedia of Integer Sequences. database
  9. F. N. Cole (1903). On the factoring of large numbers. Bulletin of the American Mathematical Society 10 (3), 134–137. doi:10.1090/S0002-9904-1903-01079-9. paper