Prime Number Checker

Using the Prime Number Checker

1. Pick a mode: the Check a Number tab tests a single integer for primality; the Find Primes Up To N tab lists every prime below a ceiling you choose.
2. Type your number in the input. Check mode accepts any positive integer up to 2⁵³-1; sieve mode accepts up to 10 million so the UI stays responsive.
3. Submit with Enter or the button. In check mode you get a yes/no result and, if the number is composite, its prime factorisation. In sieve mode you get the full list plus the count of primes found.
4. Scan the factorisation to see which small primes divide your number; this is often more useful than the yes/no answer.
5. Copy the list with the Copy All button; the output is comma-separated and pastes cleanly into a spreadsheet or a code snippet.

Under the Hood: Trial Division and the Sieve

For a single check the tool uses wheel-factored trial division: it divides by 2 and 3 first, then by numbers of the form 6k±1 up to √n. That eliminates multiples of 2 and 3 from the candidate list and gives a roughly 3x speedup over plain trial division. The algorithm is deterministic and correct for any input that fits in a JavaScript number.

For the sieve, the tool implements Eratosthenes' sieve in a Uint8Array sized to N+1 bytes. It marks 0 and 1 as composite, then for every prime p found starts crossing off multiples from p² (earlier multiples were already crossed off by smaller primes). This runs in O(N log log N) time and O(N) space. For very large N a segmented sieve or the Miller-Rabin probabilistic test would scale better, but trial division and classical Eratosthenes are exactly right for the range this tool supports.

When You Need a Prime Check

• Verifying a prime modulus when hand-rolling a Diffie-Hellman demo for a cryptography class.
• Generating a list of primes for a Project Euler problem or a programming contest solution.
• Finding the prime factorisation of a product so you can simplify a fraction or reduce a radical.
• Teaching the sieve as a first encounter with algorithmic thinking in a CS class.
• Spot-checking that a hash-table size is prime, a common rule of thumb in hash function design.
• Picking the next prime above a target, useful for load-balancing weights that must be coprime.

Edge Cases the Tool Handles

• 1 is not prime. The definition requires exactly two distinct positive divisors; 1 has only itself. Skipping this convention breaks the fundamental theorem of arithmetic because unique factorisation would fail.
• 2 is the only even prime. Every other even number is divisible by 2, so the sieve crosses them off in its first sweep.
• Carmichael numbers like 561 and 1105 fool naïve Fermat tests but are correctly identified as composite here because trial division finds their small factors directly.
• Large Mersenne-adjacent numbers are not a special case for this tool; 2³¹-1 (2,147,483,647) is prime and trial division confirms it in milliseconds.
• Inputs above 2⁵³-1 lose integer precision in JavaScript's number; for those you want a BigInt-based Miller-Rabin, not this tool.
• Zero or negative input is rejected at the UI layer; primality is only defined for natural numbers greater than 1.

Primes, Briefly

Primes are the multiplicative atoms of the integers: every positive integer larger than 1 factors uniquely as a product of primes (the fundamental theorem of arithmetic, proved by Euclid in the Elements). There are infinitely many, as Euclid showed with his famous contradiction argument. Their distribution is irregular in detail but smooth on average: the prime-counting function π(N) is asymptotic to N/ln(N), a result proved independently by Hadamard and de la Vallée Poussin in 1896 and called the Prime Number Theorem. Wilson's theorem gives a clean but impractical characterisation: p is prime if and only if (p-1)! ≡ -1 (mod p). For primality testing the modern workhorses are Miller-Rabin (probabilistic, extremely fast) and AKS (deterministic polynomial time, announced in 2002), neither of which is needed at the scales this tool targets.

When to Reach for Something Heavier

For primes beyond 10 million, segmented sieves implemented in C (primesieve) or Python with numpy vectorisation will beat a browser sieve by two orders of magnitude. For primality testing on numbers with hundreds of digits - the scale that matters for RSA key generation - you need Miller-Rabin with a curated set of witnesses, which OpenSSL and GMP ship ready to use. For fast factorisation of 20 to 60 digit composites, Pollard's rho and the elliptic curve method (ECM) in tools like YAFU or Msieve are what you want. This browser tool is the right choice when you need a fast answer for a number up to about 10¹⁵ without installing anything, and it wins on zero-install friction every time.