Prime Number Checker — Test Any Number Instantly with Steps, Factorization, Ulam Spiral & π(x) Chart

What this prime number checker does

A prime number checker answers one question: does this whole number have any positive divisor other than 1 and itself? If it does not, the number is prime. If it does, the number is composite. That definition sounds simple, but a correct answer for arbitrary input requires choosing the right algorithm — trial division for everyday numbers, a sieve when you need every prime in a range, and a deterministic variant of Miller–Rabin once the number grows past what trial division can handle in reasonable time.

This tool layers those algorithms behind a single input box. Type a number and you get an instant verdict, the exact divisor that proves compositeness when one exists, a visual proof in the form of divisor rectangles, and a numbered walkthrough of the trial division that would be performed by hand. When a number is prime, the tool shows you the bound — √n — where the search stopped, which is the part most people find hardest to reason about on paper. The tool also displays the number written in English words, in binary, octal, hexadecimal and base 36, and how long the primality test actually took on this device.

Beyond the single-number check there are six more views. Factorize breaks a composite into its prime factors and lists every divisor along with σ(n), the aliquot sum and the abundance classification, plus an amicable-pair finder and a coprime check against a second number. Range runs a sieve of Eratosthenes across any interval up to two million and renders the result as a heatmap, a density chart and a copyable list. Explore finds the neighbouring primes, measures the gap, tests for twin, cousin, sexy, Sophie Germain and safe-prime relationships, and can locate the n-th prime. Visualize draws the Ulam spiral and plots the true prime counting function π(x) against the prime-number-theorem estimate. Playground runs Goldbach partitions, Collatz sequences, Fermat test demonstrations with Carmichael numbers, and Wilson's theorem. Batch checks a whole pasted column at once and exports to CSV or JSON.

Everything runs in your browser. Numbers are parsed into BigInt the moment they exceed JavaScript's safe integer range, so a 40-digit input is handled with the same arithmetic guarantees as a 2-digit one.

What is a prime number?

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. The first primes are:

Every whole number greater than 1 is either prime or composite — there is no third option. A composite number has at least one divisor besides 1 and itself: 12 has 2, 3, 4 and 6; 100 has 2, 4, 5, 10, 20, 25 and 50.

Why 1 is not a prime number

1 sits outside both categories. It is neither prime nor composite. The reason is not arbitrary: a prime is defined as having exactly two distinct positive divisors, and 1 has only one (itself). More importantly, if 1 were prime, the fundamental theorem of arithmetic would fail. That theorem states that every integer greater than 1 has a unique prime factorization. If 1 counted as prime you could write 6 = 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3 — uniqueness would collapse. Mathematicians chose the definition that keeps the theorem clean.

Historically this was not always so. Until the early twentieth century some texts did list 1 as prime. The modern convention settled on excluding it, and every serious calculator — including this one — follows that convention.

Why 2 is the only even prime

Every even number is divisible by 2 by definition. For 2 itself, the only divisors are 1 and 2, which makes it prime. For every other even number — 4, 6, 8, 100, 1,000,000 — the divisor 2 is neither 1 nor the number itself, so those numbers are composite. That is why 2 is the single exception to the familiar shortcut "any number ending in 0, 2, 4, 6 or 8 is composite".

How to check if a number is prime

The classical method is trial division: divide the number by 2, then by 3, then by 5, and keep going until either a divisor is found or you pass the square root of the number.

The square-root stopping point is not a heuristic — it is a proof. If n = a × b with both a and b greater than √n, then a × b would be greater than √n × √n = n, which is impossible. So whenever n is composite, at least one of its factors must be less than or equal to √n. If no divisor exists up to that bound, no divisor exists at all.

Worked example: is 97 prime?

√97 ≈ 9.85, so the only divisors worth testing are 2, 3, 5 and 7.

• 97 ÷ 2 = 48 remainder 1 → not divisible by 2.
• 97 ÷ 3 = 32 remainder 1 → not divisible by 3 (digit sum 9 + 7 = 16, not a multiple of 3).
• 97 ÷ 5 ends in 7, not 0 or 5 → not divisible by 5.
• 97 ÷ 7 = 13 remainder 6 → not divisible by 7.

No divisor exists up to √97, so 97 is prime. Four divisions settle the question completely.

Worked example: is 91 prime?

√91 ≈ 9.54, so again the candidates are 2, 3, 5 and 7.

• 91 is odd → not divisible by 2.
• 9 + 1 = 10, not a multiple of 3 → not divisible by 3.
• 91 ends in 1 → not divisible by 5.
• 91 ÷ 7 = 13 exactly → divisible by 7.

So 91 = 7 × 13 and is composite. 91 is one of the most commonly misidentified numbers in school arithmetic because it looks prime, is odd, and its factors are both larger than any of the obvious small primes except 7.

Worked example: is 51 prime?

51 ÷ 3 = 17 exactly, and the digit-sum test confirms it instantly: 5 + 1 = 6, which is divisible by 3. So 51 = 3 × 17 and is composite. The same digit-sum shortcut catches 87 (8 + 7 = 15, so 87 = 3 × 29) and 57 (5 + 7 = 12, so 57 = 3 × 19).

The four algorithms this tool uses

Different inputs need different algorithms. Using a sieve to test one number is wasteful; using trial division on a 30-digit input is hopeless. The tool picks the right one automatically.

Trial division and the 6k ± 1 wheel

Plain trial division tests every integer from 2 upward. That wastes time on multiples of 2 and 3, which are trivially composite. After checking 2 and 3 explicitly, every remaining prime candidate can be written as 6k − 1 or 6k + 1 for some integer k — the numbers in between (6k, 6k + 2, 6k + 3, 6k + 4) are all divisible by 2 or 3. Testing only those two residues per block of six cuts the work by roughly a factor of three.

Sieve of Eratosthenes

To find every prime up to a limit, trial division is the wrong tool because it redoes work for each number. The sieve instead allocates a byte per number, assumes everything is prime, then walks upward: when it reaches a number still marked prime, it crosses out every multiple of that number starting from its square. Multiples below the square were already crossed out by a smaller prime, so starting at p² is both correct and necessary for the O(n log log n) running time.

This is exactly what powers the Range tab. For two million numbers the sieve finishes in a few tens of milliseconds and the memory cost is two megabytes.

Deterministic Miller–Rabin

For large numbers, trial division is not merely slow — it is hopeless. Testing a 15-digit number by trial division requires up to 31 million divisions. Miller–Rabin instead performs modular exponentiation and is correct with overwhelming probability for random bases, and provably correct when the bases are chosen carefully.

This tool uses the first twelve prime bases (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37). That set is proven to give the correct answer for every integer below about 3.18 × 10²³, which is far beyond any input a browser can meaningfully process anyway. Above that threshold the test remains an extremely strong probabilistic check rather than a proof.

Prime factorization and the fundamental theorem

The fundamental theorem of arithmetic says that every integer greater than 1 can be written as a product of primes in exactly one way, up to the order of the factors. That single fact is why prime factorization is well defined — there is no ambiguity about "the" factorization of 360.

360 = 2³ × 3² × 5. To find it by hand you divide repeatedly by the smallest prime that goes in evenly: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (so 2³); 45 ÷ 3 = 15, ÷ 3 = 5 (so 3²); 5 is prime, so it stays. Multiply back: 2 × 2 × 2 × 3 × 3 × 5 = 360.

From the factorization you can derive everything else about the divisors:

• Divisor count τ(n) = (a₁ + 1)(a₂ + 1)… For 360 = 2³·3²·5¹, τ = 4 × 3 × 2 = 24 divisors.
• Divisor sum σ(n) = (p₁^(a₁+1) − 1)/(p₁ − 1) × … For 360, σ = 15 × 13 × 6 = 1,170.
• Aliquot sum s(n) = σ(n) − n. For 360 that is 810.
• Abundance — if s(n) > n the number is abundant (360 is), if s(n) < n it is deficient (all primes and most numbers are), and if s(n) = n it is perfect (6, 28, 496, 8128…).

The Factorize tab computes all of these. Very large semiprimes — the product of two huge primes, exactly the kind used in RSA — may not factor in a browser tab, and the tool tells you that explicitly instead of hanging.

The Ulam spiral — primes along diagonals

In 1963, the Polish-American mathematician Stanisław Ulam was bored during a meeting. He started writing positive integers in a square spiral on a sheet of paper and circled the primes. To his surprise, the primes were not distributed randomly: they formed visible diagonal lines. This is the Ulam spiral, and it has been a striking visual signature of the distribution of primes ever since.

The most famous such diagonal comes from Euler's polynomial f(n) = n² + n + 41. For n = 0 the value is 41 (prime), for n = 1 it's 43 (prime), and it continues producing primes all the way to n = 39, where it finally gives 40² + 40 + 41 = 1,681 = 41². When plotted in the spiral, this whole family of values lines up along one diagonal.

You can view an interactive Ulam spiral in the Visualize tab. Slide the maximum to change how many numbers are plotted; the diagonal streaks become more pronounced as you go further out.

The prime counting function π(x) and the prime number theorem

The prime counting function π(x) is the number of primes less than or equal to x. It is not a smooth function — it increases by exactly 1 at each prime and stays flat in between — but its overall growth is remarkably regular.

The prime number theorem, proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896, says that:

That is, the ratio π(x) / (x / ln x) approaches 1 as x grows without bound. The logarithmic integral Li(x) = ∫₂ˣ dt / ln(t) is a much sharper estimate. For 10⁶ the true count is 78,498; x/ln(x) gives 72,382 (off by 8%), while Li(x) gives 78,627 (off by 0.16%).

The Visualize tab plots the actual π(x) curve alongside both estimates so you can see the convergence for yourself.

Goldbach's conjecture — every even number is a sum of two primes

In a 1742 letter to Leonhard Euler, Christian Goldbach proposed that every even integer greater than 2 can be written as the sum of two primes. The examples come easily: 4 = 2 + 2, 10 = 3 + 7, 100 = 3 + 97, 1,000 = 3 + 997. Larger numbers often have many representations.

The conjecture has been verified computationally for every even number up to at least 4 × 10¹⁸, but no general proof exists. It is one of the oldest unsolved problems in mathematics and one of the reasons the primes are still studied so actively today. The weak Goldbach conjecture — every odd number greater than 5 is the sum of three primes — was proved by Harald Helfgott in 2013 (with computational verification of the remaining case).

You can explore Goldbach partitions in the Playground tab. Enter any even number up to a few million and the tool lists every partition into two primes.

The Collatz conjecture and the primes

The Collatz conjecture (also called the 3n + 1 problem) says that if you take any positive integer and repeatedly apply the rule if odd, multiply by 3 and add 1; if even, divide by 2, you will always eventually reach 1. For 27 the sequence has 111 steps before hitting 1, reaching a peak of 9,232 along the way — a striking illustration of how chaotic even simple arithmetic can be.

The connection to primes is structural: when starting from a prime, the sequence often visits other primes, and the ways in which primes interact through Collatz-like rules remain deeply unexplained. Like Goldbach, Collatz is verified computationally far beyond any practical bound (past 2⁶⁸ as of 2025) but has no known proof. Paul Erdős famously said of Collatz: "Mathematics is not yet ready for such problems."

Special types of prime numbers

Primes are not all alike. Several named families are defined by how a prime relates to its neighbours or how it is written, and this tool flags them automatically when your number qualifies.

The Twin Prime Conjecture — that infinitely many twin primes exist — remains unsolved. The largest known twin prime pair has hundreds of thousands of digits, and the 2013 breakthrough by Yitang Zhang proved that infinitely many prime pairs exist with a bounded gap, though the bound he established was 70 million rather than 2.

Numbers that look prime but are not

A handful of composites catch people out again and again because they are odd, do not end in 5, and do not have an obvious small factor. Memorising them is genuinely useful for exams and mental arithmetic:

💡 Two-second triage. Before doing anything else, check three things: is it even (→ composite unless it is 2)? Does it end in 0 or 5 (→ composite unless it is 5)? Is the digit sum a multiple of 3 (→ composite unless it is 3)? Those three tests eliminate roughly three quarters of all composites instantly.

How many primes are there?

Infinitely many. Euclid's proof around 300 BC is one of the most elegant arguments in mathematics: assume there is a finite list of all primes, multiply them together and add 1. The result is not divisible by any prime on your list (it leaves remainder 1 in every case), so it must either be prime itself or have a prime factor not on the list — contradicting the assumption that the list was complete.

The largest known prime

As of 2026 the largest known prime is 2^136,279,841 − 1, a Mersenne prime with 41,024,320 decimal digits. It was found on 12 October 2024 by Luke Durant, a former Nvidia engineer, working through the Great Internet Mersenne Prime Search (GIMPS) project — the first record in the project's history discovered using GPUs rather than CPUs, and the first new record in almost six years.

Mersenne primes are the focus of the search because they have a dedicated primality test — the Lucas–Lehmer test — that is dramatically faster than general-purpose algorithms for numbers of that shape. Every record-holding prime since 1992 has been a Mersenne prime.

Why primes matter for cryptography

Prime numbers are not only a mathematical curiosity; they are the foundation of modern secure communication. RSA encryption — used by every HTTPS connection you make to a bank or email provider — relies on a simple asymmetry:

• Multiplying two large primes is easy. Given two 1,024-bit primes, a computer can multiply them in microseconds.
• Factoring the product back is extremely hard. Given only the 2,048-bit product, no known algorithm factors it in less than billions of years on today's hardware.

An RSA public key is exactly this product. The private key depends on the two original primes. If you could factor the product, you could break the encryption. That is why prime generation — and primality testing to confirm that the generated primes really are prime — sits at the heart of secure systems the world over.

Diffie–Hellman key exchange, elliptic curve cryptography, and other modern protocols build on related number-theoretic hard problems. Primes are the closest thing modern mathematics has to a universal one-way function.

When you actually need a prime number checker

• School and university maths. Verifying homework, checking a hand-computed factorisation, or demonstrating the √n bound in front of a class.
• Cryptography study. RSA key generation begins by picking two large primes. Understanding how primality is tested — and why Carmichael numbers matter — is foundational for understanding why the algorithm is secure.
• Hash table sizing. Many hash table implementations perform best when the bucket count is prime, because it reduces clustering with multiplicative hash functions. Finding the next prime above a chosen size is a routine step.
• Competitive programming and Project Euler. Prime checking appears in dozens of classic problems. Validating your own implementation against a known-correct one is faster than debugging it from scratch.
• Generating test fixtures. Need a prime near 10¹² for a unit test? Walk upward from the target and check each candidate.
• Cryptography-adjacent puzzles and CTFs. Recognising when a modulus is factorable is often the first step in a challenge.
• Everyday curiosity. "Is 91 prime?" is one of the most-searched number questions on the web, and the answer (7 × 13) surprises a lot of people.

Limitations

• Factorisation of very large semiprimes is not guaranteed. If you enter the product of two 50-digit primes, the tool will correctly say "composite" but may not be able to find the factors within a reasonable browser time budget. It reports that explicitly rather than freezing.
• Miller–Rabin above ~3.18 × 10²³ is probabilistic. Below that bound, with the twelve prime bases this tool uses, the result is a mathematical proof. Above it, the probability of a false positive is astronomically small but not zero.
• The range sieve is capped at 2,000,000. Larger ranges would allocate too much memory for a browser tab on low-end devices. The single-number checker has no such cap.
• The n-th prime finder is capped at the 200,000th prime (2,750,159). Beyond that the sieve bound grows faster than the interface can stay responsive.
• The Ulam spiral is capped at 40,000 numbers for canvas performance and readability. The π(x) chart is capped at 100,000 for the same reason.
• Primality is undefined for negatives, zero and non-integers. The tool explains this rather than returning a misleading "not prime".
• Browser BigInt performance varies. Very large inputs (hundreds of digits) may take a noticeable moment on older devices.

Frequently asked questions

Related calculators on AIToolsPros