Prime Number Checker & Finder
Check if a number is prime, find primes in a range, perform prime factorization, and visualize the Sieve of Eratosthenes. All calculations happen locally — nothing leaves your browser.
What is a prime number? A prime is a whole number greater than 1 whose only divisors are 1 and itself, so 2, 3, 5, 7, 11 and 13 are prime while 4, 6, 8 and 9 are not. Two is the only even prime, because every other even number is divisible by 2. Numbers greater than 1 that are not prime are called composite, and each one factors into primes in exactly one way.
How to Use the Prime Number Checker
- Test a single number — Type a value up to 999,999,999 into the Number box and press Check. The banner reports prime or composite, and the line beneath adds context such as which prime it is in sequence.
- Step to the neighbouring primes — Previous Prime and Next Prime walk to the closest prime below or above your number — the quickest way to find a prime near a target size, or to see how wide the gap between consecutive primes has become.
- Break a composite into its prime factors — The factorization panel shows the division step by step, so 360 unfolds as 2 × 2 × 2 × 3 × 3 × 5. The stat cards report the largest prime factor and how many factors there are in total.
- List every prime in a range — Set From and To (up to 10,000) and press Find to get the complete list rather than one number at a time — useful for checking a textbook table or building test data.
- Check whether two numbers are coprime — Enter any pair to see whether their greatest common divisor is 1. Coprime numbers share no prime factor, which is what makes a fraction irreducible and what RSA key generation depends on.
- Watch the Sieve of Eratosthenes run — Set a limit up to 500 and press Run Sieve to see multiples of each prime being crossed out on the grid, leaving the primes standing — the clearest way to understand why the algorithm works.
How Primality Testing Works
The obvious way to test a number is trial division: try dividing by every integer from 2 upward and see whether anything divides evenly. The key optimisation is that you never need to test past the square root of n, because if n = a × b then one of the two factors must be no larger than √n. That alone reduces the work for a nine-digit number from a billion divisions to about thirty thousand. Skipping even numbers and multiples of 3 — testing only candidates of the form 6k ± 1 — cuts it by another two thirds.
For the sizes this tool accepts, trial division is still slow enough to be noticeable, so the check uses the Miller–Rabin test instead. It works by writing n − 1 as d × 2r and examining the sequence ad, a2d, a4d … modulo n for a chosen base a. A prime forces that sequence into a specific pattern; a composite almost always breaks it, and any base that breaks it is a witness proving the number composite. Miller–Rabin is often described as probabilistic, but with a fixed set of small bases (2, 3, 5, 7, 11, 13 and up through 37) it is deterministic for every number far beyond this tool's nine-digit limit, so the verdict here is a proof, not an estimate.
Prime Factorization and the Fundamental Theorem
The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, apart from the order of the factors. That uniqueness is why primes are called the building blocks of the integers, and why the factorization panel can show a single definitive answer:
360 = 23 × 32 × 5
Factorization is found by repeated division: divide by 2 as many times as it goes, then 3, then 5, and so on up to √n. Whatever is left over at the end is itself prime. The asymmetry between how easy this is for small numbers and how hard it becomes for large ones is the foundation of RSA encryption — multiplying two 300-digit primes is instant, while recovering them from the product is beyond any known practical method.
The Sieve of Eratosthenes
To list all primes below a limit rather than test one number, the sieve is far more efficient than repeated primality tests. Write out the integers from 2 to the limit; take the first unmarked number, declare it prime, and cross out all of its multiples; repeat with the next surviving number. Once you pass √limit, every remaining unmarked number is prime. The method is roughly 2,200 years old and still the standard approach for generating prime tables.
How Common Are Primes?
Primes thin out as numbers grow, but never run out — Euclid proved there are infinitely many. The prime number theorem gives the density: the count of primes below x, written π(x), is approximately x ÷ ln(x), meaning that near a large number n roughly one in every ln(n) integers is prime.
| Limit | Primes below it, π(x) | Share of all integers |
|---|---|---|
| 10 | 4 | 40% |
| 100 | 25 | 25% |
| 1,000 | 168 | 16.8% |
| 10,000 | 1,229 | 12.3% |
| 100,000 | 9,592 | 9.6% |
| 1,000,000 | 78,498 | 7.8% |
| 1,000,000,000 | 50,847,534 | 5.1% |
The pattern of individual primes remains stubbornly irregular even though the overall density is so predictable. Twin primes such as 11 and 13 or 10,006,427 and 10,006,429 keep appearing at every scale examined so far, while stretches of hundreds of consecutive composites also occur. Whether twin primes go on forever is still an open problem.
Frequently Asked Questions
The tool handles numbers up to 999,999,999. For the range finder, the maximum is 10,000. The Sieve of Eratosthenes supports limits up to 500.
Prime factorization is expressing a number as a product of prime factors. For example, 12 = 2 × 2 × 3 = 2² × 3. Every composite number has a unique prime factorization.
Two numbers are coprime (or relatively prime) if their greatest common divisor (GCD) is 1. For example, 14 and 15 are coprime because they share no common factors other than 1.
The sieve iteratively marks the multiples of each prime starting from 2. Numbers that remain unmarked are prime. It's one of the most efficient ways to find all primes up to a given limit.
By definition a prime has exactly two distinct divisors, 1 and itself; 1 has only one divisor, so it fails. The deeper reason is the fundamental theorem of arithmetic: if 1 counted as prime, then 12 could be written as 2 x 2 x 3, or 1 x 2 x 2 x 3, or 1 x 1 x 2 x 2 x 3, and factorization would no longer be unique. Excluding 1 keeps that theorem clean.
Exact for everything this tool accepts. It uses the Miller-Rabin test with the fixed bases 2, 3, 5, 7, 11, 13 and upward, a combination that is proven deterministic for values vastly larger than the nine-digit maximum here. Miller-Rabin is only probabilistic when the bases are chosen at random, which is not what happens on this page.
No. The primality test, the factorization, the range search and the sieve animation all run in JavaScript on your device. Nothing is uploaded or logged, and the page keeps working with the network disconnected.
Use the single-number check when you have one candidate: it answers immediately regardless of size. Use the sieve or the range finder when you want every prime below a limit, because generating them all at once is far cheaper than testing each number in turn. The rule of thumb is that the sieve wins as soon as you need more than a handful of primes from the same interval.
Each panel has its own ceiling: 999,999,999 for the single check, 10,000 for the range finder, and 500 for the sieve visualisation, which has to fit on a drawn grid. Decimals and negative values are not primes by definition and are rejected. If a very large number is what you need, this tool is not the right one — cryptographic-scale primality testing needs arbitrary-precision arithmetic.
Use Cases
Checking a Factor Tree
A student who has drawn a factor tree for 1,260 compares it with the step-by-step division here to confirm every branch ended on a prime.
Simplifying an Awkward Fraction
Factoring the numerator and the denominator in turn shows exactly which primes cancel, turning 462/1,155 into 2/5 without guessing at common divisors.
Choosing a Hash Table Size
A developer takes the next prime above a target capacity, since a prime bucket count spreads keys more evenly when the hash function has hidden periodicity.
Teaching the Sieve in Class
A teacher runs the sieve to 100 on a projector so the class watches multiples of 2, 3, 5 and 7 disappear and sees why nothing beyond 10 needs testing.
Checking Two Numbers Are Coprime
Anyone learning modular arithmetic can confirm a candidate exponent shares no factor with the modulus before working through an RSA or Diffie-Hellman exercise.