What is a prime number?

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself — for example 2, 3, 5, 7, 11 and 13. Numbers greater than 1 that are not prime are called composite because they factor into smaller primes. The numbers 0 and 1 are neither prime nor composite.

Why only need to test divisors up to the square root?

If a number n has a divisor d larger than √n, then n divided by d is a matching divisor smaller than √n. So if no divisor exists at or below √n, none exists above it either, and n must be prime. This roughly halves the digits you need to search and makes trial division practical.

No. By the modern definition a prime must be greater than 1 and have exactly two distinct positive divisors. The number 1 has only one divisor (itself), so it is excluded. Treating 1 as prime would also break the fundamental theorem of arithmetic, which says every integer above 1 has a unique prime factorisation.

What is the Sieve of Eratosthenes?

It is an ancient, very fast way to list every prime up to a limit N. You start with all numbers from 2 to N, then repeatedly take the next un-crossed number as a prime and cross out all of its multiples. Whatever survives is prime. This tool runs the sieve in your browser for limits up to several million.

Is my input sent anywhere?

No. Every calculation — the primality test, the factorisation and the sieve — runs entirely in your browser using JavaScript. No number you type is ever uploaded, logged or stored on a server.

Prime Number Checker

Q: How does the checker test very large numbers so quickly?

For numbers up to about 10^11 it uses trial division by candidates of the form 6k ± 1 up to the square root, which is a complete proof. Above that it switches to a deterministic Miller–Rabin test using the witness set 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, which is proven correct for every number below 3.3 × 10^24. All arithmetic uses BigInt so nothing overflows.

A complete prime number toolkit in one page: test whether any whole number is prime or composite, break a number into its unique prime factorisation, and sieve every prime up to a chosen limit N. It is built for students learning number theory, programmers checking cryptographic-sized inputs, and anyone who just needs to know “is this number prime?” with the reasoning shown rather than a bare yes or no.

How it works

A prime number is a whole number greater than 1 divisible only by 1 and itself. Deciding primality naively means checking every possible divisor, but that is far too slow for big numbers — so the tool layers three techniques and picks the right one automatically.

First it applies a small-prime screen: if the number is divisible by any prime up to 37, it is immediately composite. For numbers up to roughly 10^11 it then runs trial division by candidates of the form 6k ± 1 only up to the integer square root √n, because any composite must have a factor at or below its square root. For larger numbers it switches to a deterministic Miller–Rabin test using the witness set 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, which is mathematically proven to give the correct answer for every integer below 3.3 × 10^24. Every divisor check and modular exponentiation uses JavaScript BigInt, so results stay exact no matter how many digits you enter.

The Factorize tab finds the unique prime factorisation guaranteed by the fundamental theorem of arithmetic. It strips small primes by trial division, sweeps the medium range with 6k ± 1 candidates, and falls back to Pollard’s rho combined with the primality test for any large remaining factor. The Primes up to N tab runs a classic Sieve of Eratosthenes, crossing out multiples of each newly found prime, to list every prime up to your limit.

Worked example

Take 360. The small-prime screen finds 360 mod 2 = 0, so it is composite. Dividing out repeatedly gives 360 = 2 × 2 × 2 × 3 × 3 × 5, which the tool reports compactly as 360 = 2^3 × 3^2 × 5. Reading the exponents back tells you, for instance, that 360 has (3+1)(2+1)(1+1) = 24 divisors.

Now test 982451653. It passes the small-prime screen, so the tool runs trial division up to √n ≈ 31344, finds no divisor, and reports it prime — it is in fact the 50-millionth prime. Finally, ask for every prime up to 100 and the sieve returns the 25 primes 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.

Formula and reference note

The square-root bound is the key shortcut: if n = a × b with a ≤ b, then a ≤ √n, so testing divisors only up to √n is sufficient. The Miller–Rabin test writes n − 1 = d · 2^s with d odd and checks, for each witness a, whether a^d ≡ 1 (mod n) or a^(d·2^r) ≡ −1 (mod n) for some 0 ≤ r < s; a witness that fails both proves n composite. The fundamental theorem of arithmetic guarantees the factorisation shown is unique up to ordering. Everything runs locally in your browser — no number you enter is ever uploaded.