Skip to content

Prime Number Checker

Is 97 prime?

Yes — prime

Estimates for educational purposes — not financial, medical, or legal advice. See terms.

Three related operations on integers: check whether a number is prime, list all primes up to a limit, or compute the prime factorisation of a positive integer. Useful in number theory homework, cryptography experiments, fraction simplification, and anywhere you need to understand a number’s prime structure.

Primality check

Given an integer n, determine whether it’s prime. The tool uses trial division up to √n with the 6k±1 optimisation: after handling 2 and 3 as special cases, every remaining prime has the form 6k+1 or 6k-1 (because any other form is divisible by 2 or 3), so the loop can skip two-thirds of the odd candidates. This runs in O(√n) time — fast enough to test any integer that fits in a JavaScript number (up to 2⁵³ ≈ 9 × 10¹⁵) in milliseconds.

Example: checking 97

Is 97 prime? Trial division: √97 ≈ 9.85, so we only need to check divisors up to 9. 97 is odd, not divisible by 3 (sum of digits = 16), not divisible by 5 (doesn’t end in 0 or 5), not divisible by 7 (97 = 13×7+6). 8 and 9 are composite (2 and 3 already checked). No divisor found → 97 is prime.

List primes up to N

Using the Sieve of Eratosthenes, the tool can list every prime up to N in a few hundred milliseconds for N up to 10 million. The sieve works by “crossing out” composites: start with 2, mark its multiples as composite; move to 3, mark its multiples; continue with each unmarked number. What remains unmarked is the set of primes. For readability, the UI truncates the displayed list at 500 entries for very large N — the full count is still shown, just not every prime.

Example: the primes ≤ 30

The sieve produces 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — the ten primes under 30. There are 25 primes under 100, 168 under 1000, 1229 under 10,000, and 664,579 under 10 million. The density of primes thins out as numbers grow (the prime counting function π(N) approaches N/ln(N) for large N), which is called the Prime Number Theorem.

Prime factorisation

Given a positive integer ≥ 2, decompose it into prime factors with their exponents. For n = 60, the factorisation is 2² × 3 × 5. For n = 1024 = 2¹⁰. For n = 2310 = 2 × 3 × 5 × 7 × 11 (the first five primes).

The algorithm is trial division by candidate primes in order, dividing repeatedly by each prime until it no longer divides, then moving on. If the remaining cofactor is still > 1 after the trial-division loop, it’s itself a prime and gets added with exponent 1.

Example: factorising 2310

2310 ÷ 2 = 1155. 1155 ÷ 3 = 385. 385 ÷ 5 = 77. 77 ÷ 7 = 11. 11 is prime. So 2310 = 2 × 3 × 5 × 7 × 11 — the product of the first five primes (also called the primorial p#(5)).

Why primality matters

Prime numbers are the atoms of number theory: every positive integer > 1 factors uniquely into primes (the Fundamental Theorem of Arithmetic). This uniqueness is why primes show up everywhere:

  • Cryptography: RSA encryption relies on the fact that factoring a large product of two primes is computationally hard. Generating RSA keys means finding big primes (typically ≥ 2048 bits).
  • Fraction simplification: To simplify a/b, divide both by GCD(a, b), which is the product of shared prime factors — the GCD / LCM calculator does that directly, and the fraction calculator builds it into every operation.
  • Hashing and pseudorandom number generation: Modular arithmetic mod a prime has nice algebraic properties that composite moduli lack.
  • Combinatorial identities: Many counting formulas factor cleanly in terms of primes.

What this tool does not do

It doesn’t do fast industrial-strength primality testing. For cryptographic-grade primes (hundreds of digits), trial division is hopelessly slow — you need Miller-Rabin, AKS, or elliptic-curve primality proving. The tool is for integers that fit in a double (up to about 9 × 10¹⁵), which is well beyond what trial division can still handle quickly.

It doesn’t handle negative or fractional numbers. Primality is defined only for positive integers > 1. The tool rejects fractional and non-integer inputs with a parse error.

It doesn’t sieve above 10 million. Memory and UI responsiveness cap the sieve. For larger ranges use a native command-line tool.

It doesn’t show the step-by-step factorisation. For “2310 ÷ 2 = 1155, ÷ 3 = 385, …” as a visual walk-through, you’d need a dedicated educational tool. The tool returns the final factorisation as a compact p₁^e₁ × p₂^e₂ × … expression.

It doesn’t handle BigInt. JavaScript’s native BigInt type supports arbitrary-precision integers, but the tool uses regular Number throughout, so inputs are limited to the safe-integer boundary.

Frequently asked questions

What is a prime number?

A positive integer greater than 1 whose only positive divisors are 1 and itself. 2, 3, 5, 7, 11, 13, 17, and so on — numbers that can't be factored into smaller pieces. Composite numbers are the ones that can (4 = 2×2, 6 = 2×3, 9 = 3×3). The number 1 is neither prime nor composite by convention — it's 'the unit', a distinct category in number theory. Zero and negative integers are also not prime under the standard definition.

How does the trial-division primality test work?

Check whether any integer from 2 up to √n divides n exactly. If one does, n is composite; if none do, n is prime. The square-root bound comes from the fact that if n has a factor greater than √n, it must also have one less than √n (because factors come in pairs). The tool optimises further: it handles 2 and 3 as special cases, then tests only candidates of the form 6k±1. After 2 and 3, every prime is of this form, so the loop can skip two-thirds of the odd numbers.

How does the Sieve of Eratosthenes work?

Write down every integer from 2 to N. Start with the smallest unmarked number (2), mark all its multiples as composite (4, 6, 8, …), then move to the next unmarked number (3) and mark its multiples (9, 15, 21, …), and so on. Every time you start marking a prime p, you can skip ahead to p² as the first unmarked multiple, because all smaller multiples (2p, 3p, …) would already have been marked when you processed 2, 3, … up to p-1. What's left unmarked is the set of primes. Runs in O(N log log N) time — fast enough to sieve up to 10 million in under a second on modern hardware.

Why cap the sieve at 10 million?

Memory and time. A 10-million-entry Uint8Array uses 10 MB, which is fine but approaching the limit of what a browser page should casually allocate. The sieve runs in a few hundred milliseconds at that size; anything larger starts to affect UI responsiveness and serialisation time for the output. If you genuinely need primes beyond that, you want a dedicated command-line tool or server-side computation, not a browser tab.

How does the factorisation work?

Trial division by successive primes. Start with 2 — divide as many times as you can, accumulating the exponent. Then try 3, 5, 7, etc. You don't actually need to find the primes in advance; just try every integer from 2 upward, and since any non-prime candidate will already have been divided out by its own prime factors, it won't divide n. Stop when p² > remaining_n; if anything is left, that remainder is itself a prime factor with exponent 1. The algorithm is O(√n) in the worst case, which is plenty fast for any integer that fits in a 64-bit float.