Prime Number Checker, Test, Sieve, Factor Any Integer

This prime number checker answers the four questions people actually ask about primes: is this single number prime?, which primes live in this range?, what is the next prime above n?, and how do I factor n into primes? It runs entirely in the browser, and it accepts integers up to nine quadrillion on plain arithmetic and switches to BigInt beyond that. Every mode uses the same underlying trial-division engine, so the result you get is consistent across the four tabs regardless of which one you happen to be looking at.

The tool is the practical counterpart to the definitions you may remember from school: a prime is an integer greater than 1 whose only positive divisors are 1 and itself. Every other integer greater than 1 is composite and can be written as a unique product of primes (the Fundamental Theorem of Arithmetic). The calculator implements that theorem directly: trial division produces the factorisation, the sieve of Eratosthenes enumerates a range, and the next-prime search simply keeps walking odd candidates until one passes the trial-division test. Everything you see on screen has been hand-verified against the canonical list in OEIS A000040, the authoritative curatorial database of prime-number sequences maintained at the OEIS by Neil Sloane and collaborators.

How to Use the Prime Number Checker

1. Pick a mode. Four buttons sit at the top of the calculator: Check primality, Primes in range, Next prime, and Prime factors. The active mode is highlighted; click another to switch.
2. Type your input. Each mode exposes its own field: a single integer for Check, lower and upper bounds for Sieve, a starting integer for Next prime, and an integer ≥ 2 for Prime factors.
3. Click the action button (Check, Sieve, Find next prime, Factorise). You can also press Enter inside any field to fire the same button without using the mouse.
4. Read the result. A boxed output panel below the inputs shows the answer, the verdict, the list, or the factorisation, plus a small explanatory line so you know what convention the calculator used (for example, that 1 is reported as "not prime" rather than as a special prime).
5. Use the quick presets. A row of preset buttons (2, 17, 97, 100, 997) lets you confirm the calculator instantly without typing.

The presets are not ornamental. They are the numbers a textbook would use to illustrate the same definitions, and they happen to hit every interesting case: 2 (the smallest prime), 17 and 97 (mid-range primes), 100 (a clean composite with prime factorisation 2² × 5²), and 997 (a prime whose index is 168). Press them in order while you are learning what the tool does; afterwards, type your own.

The calculator deliberately refuses certain inputs rather than guessing. Negative numbers, zero, blank fields, and decimal fractions all produce a clear red error message and the result box stays empty. Above Number.MAX_SAFE_INTEGER (about 9 × 10¹⁵) the check and sieve refuse to run, because ordinary JavaScript Number cannot represent every integer in that range exactly, silent rounding would let two inputs that look the same produce different answers. The boundary is chosen so the largest Number that the tool accepts has square root around 9.49 × 10⁷, which fits comfortably in an integer loop on any reasonable machine.

Is This Number Prime? The Definitions

A prime is a positive integer p > 1 such that the only positive integers dividing p are 1 and p. Every other integer ≥ 2 is composite. The number 1 is not prime, the convention goes back to Euclid, who defined primes to start above 1, and to modern usage, which leans on the Fundamental Theorem of Arithmetic: every integer ≥ 2 has a unique prime factorisation. If 1 were prime, that uniqueness would fail (you could insert any number of 1s into any factorisation without changing the product), so 1 is excluded by definition.

The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, … and there are infinitely many of them. Euclid proved that in Book IX, Proposition 20 of his Elements, around 300 BC: assume the list is finite and multiply them all together plus one; the result is not divisible by any prime on the list, so it must be divisible by a prime outside the list, which is a contradiction. The argument is the same one computer scientists reach for today when proving primality-related lower bounds.

A composite number has at least one prime divisor ≤ √n. This fact is what makes primality testing cheap: rather than trying every divisor up to n (which would be O(n)), you only have to try divisors up to √n (which is O(√n)). For n = 10⁹ that's the difference between a billion operations and roughly thirty-two thousand, about five orders of magnitude. The calculator uses this fact for every mode that touches primality testing.

How Primality Testing Works in This Tool

The trial-division primality test is the simplest correct method: for any n ≥ 2, n is prime if and only if no integer d with 2 ≤ d ≤ √n divides n. The calculator implements this with two optimisations that together speed the loop up by roughly a factor of three without changing the result.

Optimisation 1, handle small cases explicitly. If n is even, n is composite (except n = 2). If n is divisible by 3, n is composite (except n = 3). Checking those two cases before entering the loop eliminates 50% of candidates immediately and another 16.6% after that.

Optimisation 2, skip multiples of 2 and 3 with the 6k±1 wheel. Every integer greater than 3 that is not divisible by 2 or 3 has the form 6k+1 or 6k−1 for some k ≥ 1. The loop visits 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, … and at each step tests both i and i+2, which correspond to (6k−1) and (6k+1) for consecutive k. The loop bound stays √n, so the total work is roughly √n/3 divisions, about three times faster than the naive loop on every prime.

BigInt safety. For inputs above Number.MAX_SAFE_INTEGER, the calculator switches to JavaScript BigInt arithmetic. Trial division then operates on bigint values modulo bigint divisors, and √n is computed with Newton-Raphson iteration on bigint. The result is still exact, BigInt does not round, so very large inputs (up to thousands of digits in principle) are also handled correctly, although the tool caps the input field length to keep the UI responsive.

Sieve of Eratosthenes for ranges. To list every prime in [a, b], the calculator maintains a Uint8Array of size (b − a + 1), starts with every entry unmarked ("could be prime"), and for each prime p ≤ √b marks the indices of p², p² + p, p² + 2p, … as composite. After walking every prime up to √b once, the unmarked entries are exactly the primes in [a, b]. The cost is O((b − a + 1) log log b), which is essentially linear in the range length with a tiny log-log factor. The implementation uses a Uint8Array rather than a plain JS array so memory stays compact; for [1, 10⁶] the buffer is one megabyte.

Trial division for factorisation. The factoriser repeatedly extracts the smallest divisor of the current remainder: trial-divide by 2 until 2 no longer divides, then trial-divide by 3, 5, 7, … until √(current remainder). This recovers the factors in ascending order with multiplicity, which is exactly the information needed to display "2² × 3 × 5²" with exponents.

Next-prime search. Starting from max(2, n + 1), step by 1 if the candidate is even (so we are at an odd number), then keep adding 2 until the next odd number that survives trial division appears. The work is roughly the prime gap at n, which is O(log² n) on average by Cramer's conjecture refined by recent results, fewer than two hundred trial divisions for n near 10⁹.

Worked Examples

997 is prime. 997 = ?, try divisors 2, 3, 5, 7, 11, 13, … up to √997 ≈ 31.55. 2 does not divide 997 (it is odd). 9+9+7 = 25, not divisible by 3. Last digit is not 0 or 5, so not divisible by 5. 997 / 7 = 142.43, 997 / 11 = 90.6, 997 / 13 = 76.7, 997 / 17 = 58.6, 997 / 19 = 52.5, 997 / 23 = 43.3, 997 / 29 = 34.4, 997 / 31 = 32.2, none divide cleanly. So 997 is prime. It is the 168th prime in OEIS A000040.

1000 = 2 × 2 × 2 × 5 × 5 × 5. 1000 = 10³ = (2 × 5)³ = 2³ × 5³ = 2 × 2 × 2 × 5 × 5 × 5. The factoriser reports "2³ × 5³" with the exponents raised, or as plain factors [2, 2, 2, 5, 5, 5] in a list. Both views are equivalent and the calculator exposes both because factors-as-list is what you want for hand-tracing an algorithm and factorisation-with-exponents is what you want for documenting a number's structure.

Primes in [1, 30]. Sieve [1, 30]: 2 is prime, mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. 3 is prime, mark 9, 15, 21, 27. 5 is prime (already marked where it is composite), but we still walk its multiples above 25 → 25 is marked. 7 is the last prime ≤ √30. Walking the sieve leaves 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 unmarked, ten primes in [1, 30].

Next prime above 100. The candidates are 101 (odd), check 101 for divisibility by 3, 5, 7. 101 / 3 ≈ 33.7, 101 / 5 = 20.2, 101 / 7 ≈ 14.4. √101 ≈ 10.05, so we stop there. 101 is prime. The factor 100 = 2² × 5² has nothing to do with that, 101 just happens to be prime, and it is the first one after 100.

1,000,000,007 (the canonical programming modulus). Often written 10⁹ + 7, this number is prime. Try small divisors: not even, not divisible by 3 (sum of digits = 8), not divisible by 5, 7, 11, 13, 17, 19, 23, 29, 31, none work. The smallest divisor would have to be ≤ √(10⁹ + 7) ≈ 31,623, and it is more efficient to trust the modular arithmetic textbooks that cite this number as prime than to do the trial division by hand. The calculator handles it via ordinary Number since 10⁹ + 7 < Number.MAX_SAFE_INTEGER.

Why four modes, not one? A primality test that says "997 is prime" is useful, but a teaching context usually wants the next prime, the prime factorisation, and the whole list in a range. Each additional mode is roughly the same algorithm plus a different post-processing step, and combining them in one tool saves the user from copy-pasting between four separate pages. Hard cap of 1,000,000 numbers in a sieve is chosen so the buffer stays small enough to render in the result box; sieving [1, 10⁷] would work but the output would have several hundred thousand primes and would make the page hard to read.

Common Pitfalls

Treating 1 as prime. This is the single most common confusion among beginners. 1 has exactly one divisor (itself), not two; the definition of prime requires two distinct positive divisors, so 1 is neither prime nor composite. Euclid got this right in 300 BC and the convention has not changed. The calculator reports "NOT PRIME, 1 has no prime divisors" for input 1.

Going above Number.MAX_SAFE_INTEGER with Number arithmetic. JavaScript's Number can represent every integer up to 2⁵³ − 1 exactly. Beyond that, not every integer has a unique representation: 2⁵³ + 1 and 2⁵³ + 3 both round to the same Number. If you paste a 17-digit integer into a naive primality tester that uses Number arithmetic, the answer is unreliable. The calculator caps input at Number.MAX_SAFE_INTEGER for the standard modes and switches to BigInt for inputs you pass in manually above that limit.

Off-by-one in the sieve range. "Primes in [a, b]" should include both endpoints, if a or b is prime, it should appear in the output. The calculator does include both, so sieve(1, 30) shows 2 and 29 but not 31. If you want primes strictly inside (a, b), subtract 1 from b before passing it in.

Confusing primality testing with primality proving. Trial division is deterministic and correct for every integer up to the loop bound. Above ~10¹² you would normally switch to a probabilistic test (Miller-Rabin) or a deterministic one (AKS, ECPP), both are out of scope for a browser calculator. The tool is honest about this: it caps input at Number.MAX_SAFE_INTEGER and refuses larger.

Mixing up "divisor" and "multiple". A divisor d of n is a number that multiplies with another integer to give n. n % d = 0 means d divides n. A multiple of d is n × d for some integer n. Trial division is asking "which d in [2, √n] divides n?", not "which multiples of n are in some range?"

Rounding too early. A common mistake is to convert n to Number, then to BigInt, to do arithmetic. Each conversion can lose information if the original was already rounded. Always keep the original string when moving between representations and convert at the last moment.

Ignoring the exponent when reading the factorisation. 12 = 2² × 3 = 2 × 2 × 3, both are valid expressions of the same factorisation, and the calculator's "pretty" output uses the exponent form (2² × 3) for display while exposing the flat list (2, 2, 3) for programmatic use. Make sure to read the column you actually want.

Forgetting that 2 is the only even prime. Trial-division loops that just iterate by 1 waste 50% of their time on even candidates. The 6k±1 wheel optimisation in the calculator handles this for free, but if you ever hand-roll a test, watch out for it.

Where Primes Show Up

Cryptography. Public-key cryptography (RSA, Diffie-Hellman, elliptic-curve variants) rests on the difficulty of factoring large composite numbers, specifically, products of two large primes ("semi-primes"). RSA moduli in real deployments are 2048 or 4096 bits long, well beyond anything this calculator can handle, but the same trial-division algorithm appears in factorisation software as a quick preliminary filter. Primality testing is harder, but is also rare in the wild because it can be done probabilistically in milliseconds for cryptographic sizes.

Hash tables and skip lists. Most hash-table implementations size their internal arrays to prime numbers, because key distribution mod p is more uniform than mod a power of two when p is prime. Prime-sized arrays reduce clustering and improve the worst-case lookup performance. Java's HashMap uses powers of two by default, but many specialised hash structures (some Bloom filter libraries, some disk-based key-value stores) explicitly pick prime sizes.

Pseudo-random number generators. Linear congruential generators (LCGs) and the more modern Xorshift variants use prime moduli to stretch the period and reduce correlation between consecutive outputs. The Mersenne Twister uses a prime modulus (2¹⁹⁹³⁷ − 1, itself prime, the largest known prime for a long time). Picking a prime modulus means the generator cycles through all residues mod p before repeating.

Number-theoretic algorithms. Fast primality proofs (AKS, ECPP), the General Number Field Sieve (GNFS), discrete-logarithm algorithms, and most modern factoring software all spend significant time sieving ranges, walking prime lists, and constructing factor bases out of small primes. The Sieve of Eratosthenes is the seed algorithm that the rest of computational number theory grew from.

Mathematics itself. Distribution of primes, gaps between consecutive primes, prime k-tuplets, twin primes, Sophie Germain primes, every interesting phenomenon starts with the same building block. Euclid's proof that there are infinitely many primes has generated thousands of papers over two thousand years. Hardy & Wright's An Introduction to the Theory of Numbers (6th edition) is still the standard one-volume reference; the calculator's source field cites it.

Programming culture. The modulus 10⁹ + 7 = 1,000,000,007 appears in nearly every competitive-programming problem as a "modulo" instruction. It is prime, it fits in a 32-bit signed integer, and it is large enough that multiplication of two 32-bit numbers can be reduced mod 10⁹ + 7 without overflow worries. Several other prime moduli are similarly common (998,244,353 in Japan, 10⁹ + 9 for double-mod tricks). The calculator can confirm primality of any of them.

Physics and chemistry. Not directly, but prime numbers do appear in physics when energy levels are integer-quantised (energy eigenvalues in quantum harmonic oscillators are integers), and in crystallography where 5-fold symmetry was historically considered impossible because 5-fold rotational symmetry does not tile the plane with a single lattice. Quasicrystals, discovered in 1982 by Shechtman, exhibit 5-fold and other "forbidden" symmetries because their structure is ordered but not periodic, a beautiful return to the primes.

Quick Reference Table

Frequently Asked Questions

What is a prime number?

A prime number is a positive integer greater than 1 that has exactly two distinct positive divisors: 1 and itself. The smallest prime is 2; the next are 3, 5, 7, 11, 13, 17, 19, 23, and so on infinitely. By convention (going back to Euclid), 1 is not prime, because allowing 1 into the set would break the uniqueness of prime factorisations promised by the Fundamental Theorem of Arithmetic.

How do I check if a large number is prime?

For small numbers (under about 10⁹), trial division is fast enough to be interactive, try every divisor up to √n and check whether any divide evenly. For numbers up to 10¹⁵ the same trial division still works because √n is under 10⁸, which finishes in milliseconds. Above 10¹⁵ the calculator switches to BigInt to keep results exact. For cryptographic sizes (10¹⁰⁰ and beyond), you need probabilistic tests like Miller-Rabin or deterministic ones like AKS, neither of which this calculator implements because they are outside the use case of a quick browser tool.

Is 1 prime?

No. 1 is not prime, and 1 is not composite either, it sits in a category by itself called "unit". The convention is older than most of mathematics: Euclid's Elements Book VII defines a prime to be "a number which is measured by a unit alone", that is, greater than 1 with no divisor other than 1 and itself, which excludes 1 by construction. A common way to remember this: if 1 were prime, then any integer n would have multiple prime factorisations (n × 1 × 1 × …) and the Fundamental Theorem of Arithmetic would no longer be true.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an algorithm for finding all primes in a range [a, b]. It maintains a list of candidate numbers, marks 2 as prime and crosses out every multiple of 2, marks 3 as prime and crosses out every multiple of 3 that has not been crossed out already, marks 5 as prime and crosses out every multiple of 5, and continues up to √b. After processing every prime ≤ √b, every unmarked number in the range is itself prime. The algorithm runs in O((b − a) log log b) time and uses O(b − a) memory; it is the standard tool for generating prime tables in any programming language.

What is 10⁹ + 7 and is it really prime?

10⁹ + 7 = 1,000,000,007 is a prime number chosen by competitive programmers as a default modulus for arithmetic-modulo problems. It is prime (verified by hand with trial division up to √(10⁹ + 7) ≈ 31,623, by probabilistic tests in practice, and by entry in OEIS A000040-adjacent selected lists). The reason it is so popular: it is large enough that products of two 32-bit numbers stay safely below 10¹⁸, it fits in a 32-bit signed integer (just under 2³¹), and it is prime, which means every non-zero residue has a multiplicative inverse mod 10⁹ + 7. Some problems use 998,244,353 (also prime) for similar reasons.

How many primes are below n?

About n / ln n. More precisely, the Prime Number Theorem says π(n), the number of primes below n, approaches n / ln n as n grows. For n = 100, π(100) = 25 and 100 / ln 100 ≈ 21.7, close. For n = 10⁶, π(10⁶) = 78,498 and 10⁶ / ln 10⁶ ≈ 72,382, about 8% off. For very large n the approximation improves. A tighter formula by Gauss and Legendre uses the logarithmic integral li(n), which has a smaller error than n / ln n. The calculator does not compute π(n) directly, but a sieve of [2, n] gives you π(n) as the length of the returned list.

What is a twin prime?

A twin prime is a pair of primes (p, p + 2). The first few twin pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73). The Twin Prime Conjecture, still unproven, asserts that there are infinitely many twin primes. Recent work by Zhang and Maynard has shown that there are infinitely many prime pairs with gap ≤ 246, which is a major step in the direction of proving the twin prime conjecture. The calculator does not search for twin primes specifically, but a quick check on the sieve output for [a, b] will reveal them, any two primes exactly 2 apart in the list are twins.

Is there a largest prime?

No. Euclid's Elements Book IX, Proposition 20 proves that the set of primes is infinite: assume the list {p₁, p₂, …, pₖ} is the complete list and consider N = p₁ × p₂ × … × pₖ + 1. N is not divisible by any of the pᵢ (each gives a remainder of 1), so N must be divisible by some prime outside the list, which contradicts the assumption that the list was complete. Modern proofs use analytic number theory rather than Euclid's constructive argument, but the conclusion is the same: there is no largest prime. The largest known prime in 2024 is 2⁸²⁵⁸⁹⁹³³ − 1, a Mersenne prime with 24,862,048 digits, found by GIMPS in 2018.

References

• Euclid, Elements, Book IX, Proposition 20, proof that there are infinitely many primes (≈ 300 BC).
• G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 6th edition, the standard one-volume reference on elementary and algebraic number theory.
• OEIS A000040, the canonical list of prime numbers, maintained by the OEIS Foundation under Neil Sloane. The authoritative curatorial database for prime-number sequences.
• D. E. Knuth, The Art of Computer Programming, Vol. 2, §4.5.4, discussion of primality testing and the sieve of Eratosthenes.
• H. Cramér, "On the order of magnitude of the difference between consecutive prime numbers", original conjecture on prime gaps (1936).
• Y. Zhang, "Bounded gaps between primes", first proof of bounded prime gaps (2014), later improved by J. Maynard.

Related Tools

• Prime Checker, slimmer primality test with nearest-prime display.
• Prime Factorisation, dedicated factor tree with exponential-form output.
• GCD Calculator, greatest common divisor of two integers via the Euclidean algorithm.
• Fibonacci Sequence, Fibonacci numbers with BigInt precision up to F(200).
• Number Base Converter, convert between binary, octal, decimal, and hexadecimal.

Practical Tips

• Verify small cases first. Before relying on the calculator, type 2, 17, 97, 100, and 997, the presets. They should resolve in well under a second and the answers should match what every textbook says. If they do not, something is wrong upstream (an asset path, a stale bundle, a build issue) and the rest of the work is suspect.
• Refuse scientific notation and decimals. Paste plain integers (123456789) or hand-written numerals ("twelve thousand") into the calculator. Scientific notation (1.23e8) is silently rejected; decimals (3.14) are also rejected because they do not correspond to any prime or composite integer.
• Use BigInt mode deliberately. For n in the safe-integer range the tool runs on plain Number arithmetic, which is faster. For larger inputs the tool switches to BigInt, which is exact but slower, a 50-digit primality test will still feel instant, but a 1000-digit test will not. The cap on input length exists to keep the page responsive.
• Treat trial division as an upper bound, not the limit. Cryptographic primality testing is much faster than trial division because it uses number-theoretic tricks (Fermat's little theorem, Miller-Rabin, Solovay-Strassen). This calculator uses trial division because it is the most transparent method and because it is well within budget for the input sizes a UI can accept.
• Cross-check with a different tool. If the result is critical (a math paper, a code-review PR, a security-sensitive decision), confirm with a second tool that uses a different algorithm, for example, the Miller-Rabin test in Python's sympy.nextprime(..., verify=True). Both should agree on every n up to Number.MAX_SAFE_INTEGER.
• Keep a bookmark to OEIS A000040. The full prime sequence is in the public domain at the OEIS; if you ever need to look up "what is the 1000th prime?", the index page lists it directly as 7,919.