How to Check Whether a Number Is a Prime Number

Testing whether a number is prime depends on its size. For small numbers, quick mental shortcuts and pencil-and-paper trial division are fast and simple. For large numbers with tens or hundreds of digits, computers use sophisticated probabilistic and polynomial-time algorithms.

Step 1: Quick Elimination Filters

Before doing any heavy arithmetic, apply these fast rules to eliminate common composite numbers:

• Numbers ≤ 1: Negative numbers, 0, and 1 are never prime.
• Is it 2 or 3? Both 2 and 3 are prime. In fact, 2 is the only even prime number.
• Check the last digit (Even numbers > 2): If the number ends in 0, 2, 4, 6, or 8, it is divisible by 2 and therefore composite.
• Check the last digit (Multiples of 5): If the number ends in 0 or 5 and is greater than 5, it is divisible by 5 and composite.
• Sum of digits (Multiples of 3): Add up all digits of the number. If their sum is divisible by 3, the number itself is divisible by 3 and composite (e.g. for 561, 5 + 6 + 1 = 12, which is divisible by 3).

These filters cost almost nothing and remove a large share of candidates immediately. Among numbers chosen at random, the tests for 2, 3 and 5 alone rule out about 73 percent before any division takes place. Two further shortcuts are worth knowing for hand calculation:

• Divisibility by 11: Alternately add and subtract the digits from right to left. If the result is 0 or a multiple of 11, the number is divisible by 11. For 2915, the alternating sum is 5 - 1 + 9 - 2 = 11, so 2915 is composite.
• Divisibility by 7: Remove the last digit, double it, and subtract it from the remaining number. Repeat until the result is small enough to recognize. For 203, this gives 20 - 6 = 14, which is a multiple of 7.

Step 2: Trial Division (Best for Small to Medium Numbers)

Trial division is the most straightforward primality test: systematically divide the candidate number n by smaller integers to see if any divide it evenly.

The Square Root Rule (√n)

You only need to test potential divisors up to √n. If n had a divisor larger than √n, its counterpart factor must be smaller than √n. If no factor exists up to √n, the number is guaranteed to be prime.

The argument is worth stating precisely, because the rule is what makes trial division usable at all. Divisors come in pairs: if a · b = n, then finding a also reveals b. Both members of a pair cannot exceed √n, since their product would then be greater than n. Every factor pair therefore has at least one member at or below the square root, and searching that far is enough. The saving is large: proving that a twelve digit number is prime needs at most a million trial divisions rather than a trillion.

The 6k ± 1 Optimization

Every prime number greater than 3 can be written in the form 6k + 1 or 6k - 1 (where k is a positive integer). Therefore, after testing 2 and 3, you only need to test numbers of the form 6k ± 1 (i.e. 5, 7, 11, 13, 17, 19, 23, 29, 31, ...) up to √n.

The reason is that any integer falls into one of six classes modulo 6. Those of the form 6k, 6k + 2 and 6k + 4 are even, and those of the form 6k + 3 are divisible by 3, so none can be prime beyond the cases 2 and 3 themselves. Only two of the six classes survive, which cuts the work of trial division to roughly a third.

Trial Division in Code

The method translates into a short function that applies the small filters first and then steps in increments of 6:

function isPrime(int $n): bool
{
    if ($n < 2) {
        return false;
    }
    if ($n < 4) {
        return true;
    }
    if ($n % 2 === 0 || $n % 3 === 0) {
        return false;
    }

    for ($i = 5; $i <= intdiv($n, $i); $i += 6) {
        if ($n % $i === 0 || $n % ($i + 2) === 0) {
            return false;
        }
    }

    return true;
}

The loop condition compares $i with intdiv($n, $i). For positive native integers, this avoids both a floating-point square root and an overflow-prone square while preserving the exact stopping condition.

Step 3: Advanced Methods for Large Numbers

When numbers grow to dozens or hundreds of digits, trial division becomes impossibly slow because √n is astronomically large. Modern mathematics uses more powerful algorithms:

1. Fermat's Primality Test

Based on Fermat's Little Theorem, which states that if p is prime and gcd(a, p) = 1, then:

For an integer n > 1 and any base a with gcd(a, n) = 1, if a^n-1 ≠ 1 (mod n), then n is definitely composite. However, some composite numbers (called Carmichael numbers, such as 561) pass Fermat's test for every base coprime to them, necessitating stronger tests.

Composites that survive the test for a particular base are called Fermat pseudoprimes to that base. The smallest example for base 2 is 341 = 11 × 31. Carmichael numbers are the harder problem because changing among coprime bases does not help: 561 factors as 3 × 11 × 17 yet passes for every base coprime to it. Such numbers are rare but infinite in supply, a fact proved in 1994 by Alford, Granville and Pomerance.

2. Miller-Rabin Primality Test (Cryptographic Standard)

The Miller-Rabin test refines Fermat's test by examining square roots of 1 modulo n. It is a probabilistic test with two major strengths:

• It has no "Carmichael-like" blind spots; every composite number fails the test for at least 75% of chosen bases.
• By running multiple independent rounds (e.g. 24 iterations), the probability of falsely identifying a composite number as prime is at most 4^-24 ≈ 10^-15.

Miller-Rabin is a standard tool for testing candidate primes during cryptographic key generation, including the generation of RSA keys. It is also the first half of the test that powers our online prime checker, whose implementation is described in detail in Step 4 below.

The underlying idea is that in arithmetic modulo a prime, the only square roots of 1 are 1 and -1. The test writes n - 1 as d · 2^s with d odd, then squares its way up from a^d and watches for a value of 1 arriving from something other than -1. Any such occurrence proves the number composite.

For inputs below fixed thresholds the test can be made fully deterministic by using known base sets rather than random ones. Testing the bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 and 37 gives a certain answer for every number below 2⁶⁴, which covers the entire range of 64 bit integers. Many libraries also use the Baillie-PSW test, which combines one Miller-Rabin round with a Lucas sequence test. No composite has ever been found that passes it. A standing $620 bounty is often associated with Baillie-PSW, but its published conditions use related rather than identical base-2 and Fibonacci pseudoprime tests.

3. Lucas-Lehmer Test (For Mersenne Primes)

Specialized for numbers of the form 2^p - 1, where p is an odd prime. The special case p = 2 gives the prime number 3 directly. The test is deterministic and exceptionally fast. It powered GIMPS's earlier record discoveries and remains an important independent confirmation method; the 2024 record was found with an error-checked probable-prime test and then confirmed with Lucas-Lehmer tests.

The procedure starts at s = 4 and repeatedly replaces s with s² - 2 reduced modulo the candidate, running p - 2 times. For an odd prime exponent p, the Mersenne number is prime exactly when the final value is 0. Reduction modulo 2^p - 1 avoids general division: high p-bit chunks can be folded into the low chunk by addition, followed by a small final adjustment. This efficient reduction is one reason the test scales to numbers of tens of millions of digits.

4. AKS Primality Test

Published in 2002 by Agrawal, Kayal, and Saxena, AKS was the first algorithm proven to determine primality in polynomial time unconditionally and deterministically without unproven conjectures.

Its importance is theoretical: it settled the long-standing question of whether primality testing belongs to the complexity class P. In practice the constant factors are large enough that AKS is rarely used. When a genuine proof of primality is needed for an arbitrary large number, elliptic curve primality proving is the usual choice, since it produces a certificate that a third party can verify quickly.

Step 4: Implementation: How the Checker on This Site Works

Everything above is theory. Turning it into a tool that answers instantly for small numbers, keeps working on numbers thousands of digits long, and never lies about how certain its answer is, involves a series of concrete decisions. This section describes those decisions, both the mathematics and the engineering. The whole checker runs in your browser using JavaScript BigInt arithmetic, so numbers typed or pasted into the input field are not transmitted. A number supplied through the page URL is necessarily included in the page request and should not be used for private values.

Three Tiers of Certainty

No single algorithm is the right choice across the entire range. Trial division proves its answers but becomes hopeless past roughly twelve digits; Miller-Rabin is fast everywhere but only proves an answer inside verified bounds. The checker therefore splits the number line into three tiers and picks the strongest method that is still affordable:

Certainty is only surrendered at the point where it stops being purchasable at reasonable cost. Note that this applies to the prime answer alone. A composite verdict is a proof at every tier, because any base that fails the Miller-Rabin conditions is a mathematical demonstration that the number is not prime.

Tier 1: Trial Division That Proves Its Own Answer

Every candidate begins with division by the 1,229 primes below 10,000. The largest of these is 9,973, and √10⁸ = 10,000. So any number below one hundred million that survives this pass has no factor at or below its own square root, and by the square root rule of Step 2 it is prime with no further work. The pass is a complete decision procedure for that range, not merely a filter.

Above 10⁸ the same pass still earns its place. It costs roughly a thousand cheap remainder operations, and by Mertens' theorem the proportion of random integers with no prime factor below y is about e^-γ / ln y, which for y = 10⁴ is roughly 6 percent. Around 94 percent of arbitrary composites are therefore disposed of before a single modular exponentiation begins. It is also what allows the checker to name a divisor: when trial division is what rejects a number, the tool can say exactly which small prime divided it.

Tier 2: Deterministic Miller-Rabin Below 2⁶⁴

Step 3 noted that the twelve prime bases from 2 to 37 make Miller-Rabin deterministic below 2⁶⁴. That set is correct but not minimal. The checker instead uses a seven-element set found by exhaustive computer search:

These seven bases give a proven answer for every n below 2⁶⁴ = 18,446,744,073,709,551,616, using seven modular exponentiations instead of twelve. Below 3,215,031,751 the four bases 2, 3, 5 and 7 suffice, trimming it further. Notably, most of these bases are composite, such as 325 = 5² · 13. Nothing in the Miller-Rabin conditions requires prime bases; these particular values were chosen because the pseudoprimes that fool them individually have no overlap below 2⁶⁴.

The comparison with the common alternative is stark. Running 24 random rounds, a frequent library default, costs more than three times as much arithmetic and still returns only a probability bound. Inside a verified range, fixed bases are strictly better on both axes at once: less work, and a proof instead of an estimate.

Tier 3: Baillie-PSW Above 2⁶⁴

No single fixed finite base set is known to make Miller-Rabin deterministic for integers of every size. Proven base sets do cover bounded ranges beyond 2⁶⁴, but this checker's seven-base implementation is certified only through that boundary. Above it, the checker switches to Baillie-PSW, which runs three things in sequence.

A perfect square screen. The integer square root of n is computed by Newton's method and squared back. If it reproduces n, the number is composite and its root is a divisor the tool can report. This step is not merely an optimization: the Lucas test that follows searches for a parameter D with Jacobi symbol (D/n) = -1, and when n is a perfect square no such D exists. Without the screen, that search would never terminate.

A strong Miller-Rabin test to base 2. Exactly one round, as described in Step 3.

A strong Lucas test. Using Selfridge's Method A, the parameter D is taken as the first value in the sequence 5, -7, 9, -11, 13, ... whose Jacobi symbol (D/n) equals -1, and then P = 1 and Q = (1 - D) / 4. Writing n + 1 = d · 2^s with d odd, the Lucas sequences U and V are evaluated at index d. The number passes if U_d ≡ 0 (mod n), or if V_{d · 2^r} ≡ 0 (mod n) for some r in the range 0 ≤ r < s.

The reason this pairing is effective is that the two tests fail on distinct classes of pseudoprimes. Miller-Rabin base 2 fails on numbers of a particular algebraic form, while the Lucas test (built on n + 1 rather than n - 1, and operating on a quadratic field where D is a non-residue) fails on a different class. No composite integer has ever been found that passes both tests, and the search has been exhaustive below 2⁶⁴. A related $620 bounty remains unclaimed, although its published conditions are not identical to this pair of strong tests.

Measuring Work in Modular Multiplications

Because intermediate values are reduced modulo n, most multiplications in a given check operate on similarly bounded numbers. Their costs are comparable rather than identical. Counting modular multiplications therefore provides a useful implementation-based progress estimate; the percentage is tied to completed work units, while throughput and remaining time remain estimates.

A useful full-run work target can be calculated before the tests begin. Left-to-right binary exponentiation performs one squaring per exponent bit and one extra multiplication per bit that is set, so the cost of a modular exponentiation is (bits - 1) + (popcount - 1) exactly. The Lucas chain costs three multiplications per bit for the index doubling step, two more for each set bit, and two for each trailing zero of n + 1. Inputs that reach the end of both tests usually finish close to this implementation-based estimate, with the relative discrepancy shrinking for large inputs. Composites rejected early can require much less work. For sufficiently large random primes, the pair of tests averages about 5.5 modular multiplications per bit, compared with roughly 36 per bit for 24 random Miller-Rabin rounds. That is about 6.5 times fewer modular multiplications; the wall-clock speedup depends on the BigInt implementation and the size of the input.

Why the Code Avoids Decimal Conversion

A detail that matters far more than it looks. Converting a BigInt to or from a decimal string is superlinear in the number of digits, because 10 is not a power of 2. Converting to binary or hexadecimal is linear, since each digit maps to a fixed block of bits. Any code path that touches a decimal representation of a large number repeatedly will crawl.

The implementation therefore takes exponent bits from toString(2), derives bit length from toString(16) combined with Math.clz32, and counts the digits of your input by measuring the string you typed rather than by converting the parsed number back. Exponentiation itself is driven straight off the binary string:

function modPowBits(base, bits, m) {
    let r = base % m;                     // bits[0] is always '1'
    for (let i = 1; i < bits.length; i++) {
        r = (r * r) % m;                  // one squaring per bit
        if (bits[i] === '1') {
            r = (r * base) % m;           // one multiply per set bit
        }
    }
    return r;
}

The Lucas chain is driven by the same string, walking the binary expansion of d and applying a doubling step at every bit and an increment step at every set bit:

U = (U * V) % n;                          // index k -> 2k
V = (V * V - 2n * Qk) % n;
Qk = (Qk * Qk) % n;

if (bits[i] === '1') {                    // index 2k -> 2k + 1
    const Un = half(U + V, n);
    const Vn = half(D * U + V, n);
    U = Un;
    V = Vn;
    Qk = (Qk * Q) % n;
}

The half helper divides by 2 modulo an odd n: reduce the value, add n if the result is odd, then shift right by one bit. Both Un and Vn must be computed from the old values before either is assigned, which is the easiest place in the whole algorithm to introduce a silent bug.

Keeping the Page Responsive

A check on a number with several thousand digits can run for seconds or minutes, and JavaScript arithmetic cannot be interrupted mid-operation. Three mechanisms keep the interface usable.

• Size-based routing. Anything below 2⁶⁴ is decided on the main thread, where it usually completes without a perceptible delay. For inputs in this range, background-thread messaging would often add more overhead than the arithmetic itself.
• A persistent Web Worker. Larger numbers go to a worker that is created once when the page loads and kept alive between checks, so no start-up cost is paid per query. It streams progress back roughly every tenth of a second.
• Termination as the abort mechanism. Because the worker is inside a synchronous loop, it cannot check a stop flag. Pressing Stop terminates the worker outright and immediately spawns a replacement, so the next check still starts warm.

What the Answer Actually Claims

The two possible verdicts do not carry the same weight, and the checker is explicit about which one you are looking at.

A composite verdict is always a proof. A failed Miller-Rabin or Lucas condition is a mathematical demonstration that the number cannot be prime, with no probability attached. What such a proof does not supply is a factor: the test establishes compositeness without ever finding one, which is why the tool names a divisor only when trial division or the perfect square screen happened to turn one up.

A prime verdict depends on the tier. Below 2⁶⁴ it is a proof, and the result says so. Above that threshold it is a Baillie-PSW certification: overwhelming evidence, backed by decades of unsuccessful searching, but not a proof. Producing a genuine proof for an arbitrary number of that size means elliptic curve primality proving, which is a different and considerably more expensive undertaking.

Summary Comparison

Common Mistakes

• Treating 1 as prime. It is a unit, neither prime nor composite, and including it would break unique factorization.
• Stopping the search at n / 2. This is correct but wasteful, since the square root bound is far tighter.
• Trusting a single passing Fermat round. Carmichael numbers pass for every base coprime to them, so a pass does not establish primality. A failed round, however, proves that the number is composite.
• Using floating point or an overflow-prone square for the bound. For positive native integers, comparing i <= intdiv(n, i) avoids both rounding and overflow.
• Reading a probabilistic pass as proof. A failed Miller-Rabin round proves compositeness, but passes to randomly chosen bases indicate only probable primality. A complete pass over a fixed base set proven sufficient for a particular range is deterministic throughout that range.
• Using random bases where fixed ones are proven. Below 2⁶⁴, random rounds do more work for a weaker guarantee.
• Converting large numbers to decimal inside a loop. Decimal conversion is superlinear; binary and hexadecimal are not.

Test Your Numbers Online

You can use our browser-based Prime Number Check for whole integers up to 20,000 decimal digits. Small inputs return immediately; very large inputs may take seconds or minutes. You can also explore our guides to the Sieve of Eratosthenes and the different types of prime numbers.