Sprint 8 Converter + Math
Prime Number Checker
Basic primality check.
Result
Not prime
How it works
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Primes are the "atoms" of arithmetic — every integer greater than 1 can be expressed as a unique product of primes (the Fundamental Theorem of Arithmetic). The Prime Number Checker determines instantly whether a number is prime and, if composite, returns its prime factorisation.
**How primality testing works** For small numbers (< 10¹⁵), trial division is fast enough: test all primes up to √n. If none divide n, then n is prime. The square root bound works because if n = a × b, at least one of a or b must be ≤ √n. The checker uses an optimised 6k ± 1 sieve — all primes greater than 3 are of the form 6k − 1 or 6k + 1, eliminating 2/3 of trial divisors immediately.
**Notable prime facts** - The only even prime is 2. - 1 is not prime by convention (would break unique factorisation). - Twin primes differ by 2: (3,5), (5,7), (11,13), (17,19). Whether there are infinitely many twin primes is unsolved (the Twin Prime Conjecture). - The largest known prime (as of 2024) is a Mersenne prime: 2¹³⁶²⁷⁹⁸⁴¹ − 1, with over 41 million digits. - Mersenne primes have the form 2ᵖ − 1 where p is also prime.
**Applications** RSA encryption relies on the difficulty of factoring large semiprime numbers (products of two large primes). Key sizes of 2048 or 4096 bits mean primes with 600–1200 digits. Hash functions (SHA-256) and random number generators also use prime numbers in their internal structure.
Privacy: all primality checking runs in the browser. No data is transmitted.
Frequently Asked Questions
- No. By modern mathematical convention, 1 is neither prime nor composite. The reason: the Fundamental Theorem of Arithmetic states every integer > 1 has a unique prime factorisation. If 1 were prime, factorisation would not be unique (e.g., 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, etc.). Excluding 1 from primes preserves unique factorisation. This was not always the convention — historically some mathematicians did call 1 prime.
- RSA works by multiplying two large primes p and q to create a public modulus n = p × q (typically 2048 bits = ~617 digits). Encryption uses the public key; decryption requires knowing p and q separately. The security relies on the fact that factoring a large semiprime n back into p and q is computationally infeasible — the best known classical algorithms would take longer than the age of the universe for 2048-bit keys. Quantum computers running Shor's algorithm could factor them efficiently, which is why post-quantum cryptography is an active research area.
- Yes — Euclid proved this around 300 BCE with an elegant proof by contradiction: assume there are finitely many primes p₁, p₂, ..., pₙ. Construct N = (p₁ × p₂ × ... × pₙ) + 1. N is either prime itself, or it has a prime factor not in the original list (since dividing N by any pᵢ leaves remainder 1). Either way, a prime exists outside the original list — contradiction. Therefore infinitely many primes exist.
- For numbers up to ~3.3 × 10²⁴, the Miller-Rabin primality test with specific deterministic witness sets provides a definitive answer (not probabilistic). For numbers with hundreds of digits, probabilistic Miller-Rabin (with many random witnesses) gives answers with error probability below 4⁻ᵏ for k rounds. The AKS algorithm (2002) was the first provably polynomial-time deterministic primality test but is slower in practice than optimised Miller-Rabin for typical key sizes.