Prime Number Checker
Check primality, find primes in a range, and compute prime factorizations
Enter a Number
Type any number up to 999,999 in the field above
Result
Prime Number Checker
Check primality, find primes in a range, and compute prime factorizations
Guide
How it works
Prime numbers are the atoms of arithmetic — the indivisible building blocks from which all integers are constructed. A prime number is a whole number greater than 1 that has exactly two distinct positive divisors: 1 and itself. The number 17 is prime because only 1 and 17 divide it evenly. The number 15 is not prime because it factors as 3 times 5.
The Fundamental Theorem of Arithmetic
One of mathematics' most elegant results is the Fundamental Theorem of Arithmetic: every integer greater than 1 can be represented as a product of prime numbers in exactly one way (up to the order of factors). This unique prime factorization makes primes the universal "DNA" of integers. The number 360 = 2³ × 3² × 5, and no other combination of primes produces 360. This uniqueness underlies vast swaths of number theory, algebra, and cryptography.
How Many Primes Are There?
Euclid proved over 2,300 years ago that infinitely many primes exist, using one of mathematics' most elegant proofs by contradiction. Assume there are finitely many primes p₁, p₂, ..., pₙ. Form the number N = (p₁ × p₂ × ... × pₙ) + 1. Either N is prime (contradicting our assumption) or N has a prime factor not in our list (also contradicting our assumption). Therefore no finite list can contain all primes. The prime counting function π(n) — how many primes exist up to n — grows approximately as n / ln(n), a result formalized in the Prime Number Theorem proved independently by Hadamard and de la Vallée Poussin in 1896.
The Sieve of Eratosthenes
The ancient Greek mathematician Eratosthenes (c. 276-194 BCE) devised an elegant algorithm for finding all primes up to a given limit. Start with all numbers from 2 to N. Mark 2 as prime, then cross out all its multiples. Move to the next unmarked number (3), mark it prime, cross out its multiples. Continue until you reach √N — every remaining unmarked number is prime. The algorithm runs in O(n log log n) time and remains one of the most efficient methods for generating primes in bulk, still used in competitive programming and cryptographic applications today.
Primality Testing at Scale
The trial division method used here works well for numbers up to a few million but becomes impractical for very large numbers. Modern cryptographic applications (RSA encryption, for instance) require working with primes of hundreds of digits. The Miller-Rabin primality test, a probabilistic algorithm, can verify primality of such numbers in milliseconds. For deterministic verification, the AKS primality test (2002) was a landmark achievement — the first polynomial-time deterministic algorithm — though Miller-Rabin remains faster in practice.
Primes in Cryptography
The entire RSA cryptosystem, which secures much of internet communication, depends on the computational asymmetry between multiplication and factorization. Multiplying two large primes together takes milliseconds. Factoring the result back into those two primes — given only the product — takes classical computers longer than the age of the universe for sufficiently large numbers. Your browser's HTTPS connection, banking transactions, and encrypted emails all rely on this one-way mathematical trapdoor. Quantum computers running Shor's algorithm would break RSA, which is why post-quantum cryptography standards are now being developed.
Unsolved Problems in Prime Theory
Despite millennia of study, primes remain deeply mysterious. The Goldbach Conjecture (1742) states that every even integer greater than 2 is the sum of two primes — verified computationally to 4 × 10¹⁸ but never proven. The Twin Prime Conjecture holds that there are infinitely many pairs of primes differing by 2 (like 11 and 13, or 17 and 19) — significant progress was made in 2013 when Yitang Zhang proved infinitely many prime pairs exist within a bounded gap, but the conjecture remains open. The Riemann Hypothesis, arguably the most important unsolved problem in mathematics, makes a precise claim about the distribution of prime numbers in the complex plane. It carries a $1 million Millennium Prize.
What makes a number prime?expand_more
A prime number is any whole number greater than 1 that has exactly two divisors: 1 and itself. The number must not be divisible by any integer other than these two. By this definition, 1 is not prime (it has only one divisor), and 2 is the only even prime.
How do you check if a large number is prime?expand_more
The simplest method is trial division: test whether the number is divisible by any integer from 2 up to its square root. If no divisor is found, it is prime. You only need to check up to the square root because if n = a × b and both a and b are greater than √n, then a × b would exceed n. For very large numbers, probabilistic tests like Miller-Rabin are used instead.
What is prime factorization used for?expand_more
Prime factorization has widespread applications: computing the greatest common divisor (GCD) and least common multiple (LCM) of numbers, simplifying fractions, solving modular arithmetic problems, and most importantly, forming the mathematical foundation of RSA public-key cryptography. The difficulty of factoring large semiprimes (products of two large primes) secures most internet communications.
Are there patterns in prime numbers?expand_more
Primes become less frequent as numbers grow larger, following the Prime Number Theorem (the density near n is approximately 1/ln(n)). However, their exact distribution contains deep structure described by the Riemann zeta function. Primes often appear in patterns like twin primes (differing by 2), cousin primes (differing by 4), and sexy primes (differing by 6), but whether infinitely many such pairs exist for each gap size remains mostly unproven.
What are the first few prime numbers?expand_more
The first 25 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The number 2 is the only even prime — all larger even numbers are divisible by 2 and therefore composite.
Next steps