Prime Number Checker

⚡ Quick Tips for Checking Primes Correctly

Features

Why Trial Division Alone Isn't Enough Anymore

Trial division — testing whether a number divides evenly by everything up to its square root — is exact and easy to understand, and it's genuinely the fastest method for small numbers. But its runtime grows with the square root of the input, so every two extra digits in the number roughly multiplies the search by ten. For anything beyond a few trillion, that becomes noticeably slow, which is exactly where most free prime checkers quietly cap their input size. This tool switches to the Miller–Rabin test instead, which checks a number's behavior under modular exponentiation rather than searching for factors directly — a fundamentally different approach that stays fast regardless of how large the number gets.

The distinction matters in practice, not just in theory: 9,007,199,254,740,881 — a prime sitting just below JavaScript's safe integer limit — verifies correctly here in a fraction of a second, and so does a number ten times that size. A calculator built purely on trial division, or one built on ordinary numbers instead of BigInt, would either take far too long or return a silently wrong answer for inputs at that scale, since ordinary floating-point numbers stop representing integers exactly well before that point is reached.

Primes Are the Atoms of Every Whole Number

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime itself or breaks down into a product of primes in exactly one way, ignoring order — 84 is always 2² × 3 × 7 and never anything else. That uniqueness is what makes prime factorization useful rather than just decorative: it's the same operation underneath reducing a fraction to lowest terms, since dividing a numerator and denominator by their shared prime factors is exactly how a fraction like 84/126 simplifies down to 2/3. The Fraction Calculator performs that reduction automatically using the same underlying factorization this tool displays explicitly.

This is also why 1 sits outside the primes entirely, despite looking harmless enough to include. If 1 counted as prime, 12 could be written as 2²×3, or 1×2²×3, or 1⁵⁰⁰×2²×3 — infinitely many "valid" factorizations for the same number, which would break the uniqueness the entire theorem depends on. Excluding 1 isn't an arbitrary rule handed down for convenience; it's the specific condition that keeps prime factorization meaningful at all.

The Trap That Catches Weaker Primality Tests

A simpler and much older method, Fermat's little theorem, checks whether a^(n−1) ≡ 1 (mod n) for some base a — usually a good sign of primality, but not a guarantee. A small set of composite numbers called Carmichael numbers, the smallest being 561, 1105 and 1729, pass that test for every possible base, fooling Fermat's method into reporting them as prime when they are not. Miller–Rabin was specifically designed to close this gap, and correctly flags every known Carmichael number as composite — a detail worth knowing if comparing this tool's results against a simpler homemade script that only implements the Fermat check.

Who Actually Reaches for a Prime Number Checker

Students verifying number theory homework across both primality and factorization, not just a single yes/no answer. Programmers testing edge cases for a primality function they're writing themselves, using this as a known-correct reference before trusting their own code. Puzzle and math enthusiasts exploring prime deserts, twin prime pairs, or how prime density thins out as numbers grow, using Range mode to generate a working list rather than checking candidates one at a time. Anyone curious about cryptography wanting to see firsthand why factoring a large composite is so much harder than testing whether it's prime in the first place — the exact asymmetry this tool's factorization cutoff demonstrates directly. For finding the GCD or LCM once two numbers' factorizations are known, the LCM & GCD Calculator picks up from there.

Two Things Worth Trying

Watching primes thin out: run Range mode on 1–1,000, then on 9,000–10,000 — both are 1,000-number windows, but the first contains 168 primes while the second contains noticeably fewer. This is the Prime Number Theorem in action: primes get rarer as numbers grow, roughly following N / ln(N), even though — as Euclid proved over two thousand years ago — they never stop appearing entirely.

Finding a Carmichael number's real factorization: check 561 in Check mode. It reports composite immediately (correctly resisting the classic Fermat-test trap), and the factorization panel shows exactly why: 561 = 3 × 11 × 17. Seeing the real factors alongside the correct classification makes the earlier point about weaker primality tests concrete rather than abstract, and it's a genuinely useful check to run against any homemade primality script before trusting it on larger inputs.

Why Browser-Based Beats a Textbook Prime Table

A printed table of the first thousand primes covers exactly that — a thousand primes, fixed at print time. This tool generates a fresh list for any range on demand, tests any single number regardless of size, and runs the entire Miller–Rabin and sieve computation client-side in JavaScript, with nothing entered ever sent to a server. For factoring a number as part of finding a shared denominator across several numbers at once, the LCM & GCD Calculator's multi-number mode handles that directly instead of checking factors one number at a time here.

Where This Calculator Draws the Line

It tests primality at any size and factors composites up to one trillion — it doesn't implement specialized large-number factoring algorithms like the quadratic sieve or Pollard's rho, which is exactly why factorization is capped rather than attempted for every input regardless of size. For general arithmetic once a number's primality or factors are known, the Scientific Calculator covers the rest.