🔍 Prime Number Checker

🔧 Operation

📝 Number to test

Integer between 1 and 264. Pass values above Number.MAX_SAFE_INTEGER as a digit string. Factorization is shown for composites up to 1012.

📝 Range

Range span up to 100,000. Upper bound capped at 108.

📝 Number

Integer up to 264. "Previous" returns nothing when n ≤ 2.

📤 Result

{{ checkResult.n }} is PRIME {{ checkResult.n }} is COMPOSITE
Reason: {{ checkResult.reason }}

Prime Factorization

{{ checkResult.n }} = {{ factorsToText() }}
Previous prime: {{ checkResult.previousPrime }} —
Next prime: {{ checkResult.nextPrime }}

📤 Primes in range

Found {{ listResult.count }} primes in [{{ listResult.from }}, {{ listResult.to }}]
{{ listResult.primes.join(', ') }}

📤 Result

No previous prime exists for n = {{ npResult.n }} Next prime after {{ npResult.n }} → {{ npResult.prime }} Previous prime before {{ npResult.n }} → {{ npResult.prime }}

Result will appear here as you type.

⚠️

ℹ️ About Prime Number Checker

What is a prime number?

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. The sequence begins 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … (OEIS A000040). The number 1 is by convention not prime so that the Fundamental Theorem of Arithmetic — every integer above 1 factors uniquely into a product of primes — holds without exception.

This tool offers three operations:

  • Check — decide whether a single integer n is prime, with factorization when it is composite and small enough.
  • List — enumerate every prime in a range [from, to] using a segmented Sieve of Eratosthenes.
  • Next / Previous Prime — find the closest prime greater than or less than n.

For broader context, the prime sequence is cataloged by OEIS A000040, and the PrimePages project maintains references and tables for known primes, primality proofs, and educational number-theory material.

Primality Testing Methods

The checker switches algorithm based on the size of the input so it stays both fast and deterministic:

  • Trial division — for n ≤ 1012. Candidate divisors run from 2 up to √n using a 6k±1 wheel. When n is composite, the trial loop doubles as a full prime factorization.
  • Deterministic Miller-Rabin — for 1012 < n ≤ 264. Uses the witness set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}, which is proven deterministic for every n < 3.317 × 1024 (Sorenson & Webster, 2015) — well above our cap. Above 1012 factorization is skipped because trial division becomes too slow to keep the browser responsive.
  • Above 264 the input is rejected. JavaScript's BigInt can hold the value but the deterministic witness set used here is only proven down through that range.

Sieve of Eratosthenes

For prime listing, a segmented Sieve of Eratosthenes marks the multiples of every prime up to √to against a bitmap covering only the requested window [from, to]. The remaining indices are prime.

Time complexity is O(N log log N) with N = to - from + 1, the textbook lower bound for sieve-based enumeration.

The range span is capped at 100,000 entries and the upper bound at 108 to keep responses bounded and interactive. Outside these limits the tool returns an explicit error rather than blocking the page.

Use Cases

  • Cryptography — RSA, Diffie-Hellman, and DSA all generate large random primes for their key material; NIST's FIPS 186-5 discusses prime generation and validation requirements for digital signatures.
  • Hash table sizing — choosing a prime bucket count reduces clustering on power-of-two-aligned inputs.
  • Number-theoretic transforms — FFT-over-finite-fields uses primes of the form p = c · 2k + 1 for efficient modular arithmetic.
  • Math curriculum — classroom exploration of factorization, prime gaps, twin primes, and Mersenne primes.
  • Pseudo-random sequence design — LCG modulus choice, full-period generator analysis.
  • Programming puzzles & competitive coding — quick reference for Project Euler, Codeforces, and Advent of Code style problems.

Worked Examples

  • check(97) → prime; previous prime 89, next prime 101.
  • check(100) → composite; factorization 2² × 5².
  • check(1) → not prime (by definition).
  • check(982451653) → prime (a famous 32-bit prime used in hashing examples).
  • listPrimes(1, 30) → [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], count 10.
  • listPrimes(100, 200) → 21 primes (cross-checked against the UTM primes list).
  • nextPrevPrime(100, "next") → 101; nextPrevPrime(2, "prev") → null.

References

  • Sorenson, J. and Webster, J. (2015), Strong Pseudoprimes to Twelve Prime Bases, Mathematics of Computation 86 (304), 985-1003 — proves the deterministic witness set used by this tool.
  • Wikipedia: Miller-Rabin primality test.
  • Wikipedia: Sieve of Eratosthenes.
  • UTM Prime Pages: First 1000 primes (cross-check source for our test vectors).
  • OEIS A000040 — the prime sequence.

API Usage Example:

POST /api/tools/math/prime-number-checker
Content-Type: application/json

{
    "operation": "check",
    "n": 97
}
Ready