How does the primality test work?

This calculator uses the deterministic Miller-Rabin primality test with the witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}. This set is provably sufficient for all integers up to about 3.3 × 10²⁴ - far beyond what JavaScript can represent exactly as a Number. The algorithm uses BigInt arithmetic for correctness.

How does prime factorization work?

For small numbers, the calculator uses trial division (checking divisibility by all primes up to √n). For large semiprimes and composites, it uses Pollard's rho algorithm - a probabilistic factorization method that is much faster than trial division for large numbers. The result is always exact.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an ancient algorithm that finds all primes up to a limit N. It works by iteratively marking the multiples of each prime as composite. This calculator's implementation uses a Uint8Array for memory efficiency and runs up to 10 million in your browser in under a second.

How many primes are there up to 10 million?

There are 664,579 primes up to 10 million. The prime counting function π(n) grows roughly as n / ln(n) - this is the Prime Number Theorem. At 1 million there are 78,498 primes; at 100,000 there are 9,592.

Prime Number Tools - Primality Test, Factorization & Sieve

About prime numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. There are infinitely many primes. Euclid proved this around 300 BCE. Prime numbers are the building blocks of all natural numbers through the Fundamental Theorem of Arithmetic: every integer greater than 1 can be expressed uniquely as a product of primes.

Miller-Rabin primality test

This calculator uses the deterministic Miller-Rabin algorithm with a fixed set of witnesses that is proven sufficient for all integers up to about 3.3 × 10²⁴. The test is based on properties of Fermat's little theorem and is much faster than trial division for large numbers. It uses JavaScript BigInt for exact arithmetic.

Fundamental Theorem of Arithmetic

Every integer greater than 1 is either prime itself or can be written as a unique product of prime powers. For example, 360 = 2³ × 3² × 5. This decomposition is unique (up to ordering) and is the basis for many results in number theory. This calculator finds that decomposition using trial division and Pollard's rho algorithm for large composites.

Prime counting function

The prime counting function π(x) counts the number of primes ≤ x. The Prime Number Theorem states that π(x) ≈ x / ln(x) as x grows large. This means primes become progressively sparser: there are 25 primes below 100, but only ~78,498 primes below 1,000,000. The ratio of primes to integers around x is roughly 1/ln(x).

Famous primes

Largest known prime (2024): 2^136,279,841 − 1, a Mersenne prime with over 41 million digits, discovered by GIMPS (Great Internet Mersenne Prime Search).
Twin primes: pairs of primes differing by 2 (e.g., 11 & 13, 17 & 19). Whether there are infinitely many twin primes is an open problem (the Twin Prime Conjecture).
Sophie Germain primes: a prime p where 2p + 1 is also prime (e.g., p = 11 gives 2p + 1 = 23). Used in certain cryptographic protocols.

Prime factorization and cryptography

RSA encryption — the cryptosystem securing most HTTPS connections — relies on the computational hardness of factoring the product of two large primes. Multiplying two 2048-bit primes takes microseconds; factoring the result is computationally infeasible with current technology. This asymmetry between multiplication (easy) and factoring (hard) is the mathematical foundation of public-key cryptography.