Prime Number Checker & Generator

About the Prime Number Checker & Generator

Type a whole number — or an expression such as 2^61 − 1, 10^100 + 267 or 30! + 1 — to find out whether it is prime. Numbers below 3,317,044,064,679,887,385,961,981 (about 3.3 × 10²⁴) are decided with certainty: the Miller–Rabin test with the first 13 prime bases is known to make no mistakes in that range. Larger numbers, up to 1,000 digits, get the Baillie–PSW test. It has no known counterexample, but it is not a proof, so a pass is labelled probable prime.

For a composite number you see its smallest prime factor and, when it can be found, the full prime factorisation. Other modes find the next and previous primes of any number, the nth prime up to n = 10¹¹, the number of primes up to 10¹² — π(x) — and every prime or twin prime in a range. Everything runs in your browser, in a background thread you can stop at any time.

Common uses

• Checking homework on primes, factors and prime factorisation.
• Getting test values for programs: large primes, Carmichael numbers, strong pseudoprimes.
• Exploring prime gaps, twin primes and how closely π(x) follows x ÷ ln x.

How primality is decided

• Small numbers are divided by every prime up to their square root.
• Below about 3.3 × 10²⁴, the Miller–Rabin test (Miller 1976; Rabin 1980) is run with the first prime bases. Most composite numbers fail it for every base, but some pass for a few bases — strong pseudoprimes. The smallest composite that passes for all of the first 13 primes, 2 to 41, is 3,317,044,064,679,887,385,961,981 (Sorenson & Webster 2017), so below it the test is a proof. Smaller numbers need fewer bases: below 2⁶⁴, the twelve primes 2 to 37 are enough.
• Above that, the tool uses Baillie–PSW: a strong probable-prime test to base 2 followed by a strong Lucas probable-prime test with Selfridge’s parameters (Baillie & Wagstaff 1980). The two tests fail in unrelated ways, and no composite number that passes both has ever been found — but no one has proved that none exists, so these results are called probable primes.

Finding factors

Composite numbers are first divided by small primes; the first one that divides is the smallest prime factor. What is left is split with Pollard’s rho method, which quickly finds factors of up to about 12–15 digits, and each piece is tested for primality, so a complete factorisation lists only primes. Splitting a product of two very large primes, as in an RSA key, is beyond any browser tool: the number is still shown to be composite, but its factors are not found.

Counting and listing primes

π(x), the number of primes up to x, is computed exactly with a refinement of Legendre’s method (Lucy Hedgehog’s algorithm); π(10¹²) = 37,607,912,018 takes about a second on a typical computer. The prime number theorem says π(x) is close to x ÷ ln x and closer still to the logarithmic integral li(x); both estimates are shown next to the exact count. Lists use a segmented sieve of Eratosthenes. Twin primes are pairs that differ by 2, such as 11 and 13 — whether there are infinitely many is still an open problem.

Sources

• Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences 13: 300–317.
• Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory 12: 128–138.
• Baillie, R. & Wagstaff, S. S. (1980). Lucas pseudoprimes. Mathematics of Computation 35: 1391–1417.
• Sorenson, J. & Webster, J. (2017). Strong pseudoprimes to twelve prime bases. Mathematics of Computation 86: 985–1003.

Limitations

• Check accepts numbers of up to 1,000 digits. The neighbouring primes are found automatically for numbers of up to 400 digits; use Next & previous for larger ones.
• Above 3.3 × 10²⁴ a prime is a probable prime (Baillie–PSW), not a proven one. Proving that a very large number is prime needs a dedicated method such as elliptic-curve primality proving (ECPP).
• Factorisation stops after a few seconds. A number whose prime factors all have more than about 15 digits is shown as composite without its factors.
• The nth prime works up to n = 10¹¹ and counting up to x = 10¹². Lists go up to 10¹⁵, for ranges of up to 100 million numbers (10 million above 10¹²); above 10¹⁵ a list can cover 10,000 numbers. At most 200,000 primes are listed or downloaded at once.

Privacy

Everything happens in your browser. What you enter or open here is not uploaded or stored by MySmartCoPilot.