Prime Number Checker
Check if any number is prime.
If not, see its full prime factorization.
Also shows the nearest primes above and below for quick number theory reference.
Prime numbers are integers greater than 1 that have no positive divisors other than 1 and themselves. Prime factorization breaks any composite number into a unique product of primes — a property guaranteed by the Fundamental Theorem of Arithmetic.
Primality test (trial division): To check if n is prime, test divisibility by all integers from 2 up to √n. If none divide n evenly, n is prime.
Why √n suffices: If n = a × b and both a and b are greater than √n, then a × b > n — a contradiction. So at least one factor must be ≤ √n.
Prime factorization algorithm:
- Start with the smallest prime (2)
- Divide the number by 2 as many times as possible
- Move to 3, then 5, then 7… (skipping evens after 2)
- Continue until the remaining quotient equals 1
- All divisors collected are the prime factors
GCD using prime factorization: GCD(a, b) = Product of common prime factors at their minimum exponents
LCM using prime factorization: LCM(a, b) = Product of all prime factors at their maximum exponents
Prime number density: The Prime Number Theorem states that the number of primes less than n is approximately: π(n) ≈ n ÷ ln(n)
- Primes below 100: 25 primes
- Primes below 1,000: 168 primes
- Primes below 10,000: 1,229 primes
Notable primes:
- Mersenne primes: 2^p − 1 (e.g., 3, 7, 31, 127, 8191…)
- Twin primes: pairs differing by 2 (e.g., (11,13), (17,19), (41,43))
- Largest known prime (2024): 2^136,279,841 − 1 (over 41 million digits)
Worked example — prime factorization of 360: 360 ÷ 2 = 180 180 ÷ 2 = 90 90 ÷ 2 = 45 45 ÷ 3 = 15 15 ÷ 3 = 5 5 ÷ 5 = 1
Prime factorization: 360 = 2³ × 3² × 5¹
GCD(360, 252): Factorize 252 = 2² × 3² × 7 Common factors: 2² × 3² = 4 × 9 = GCD = 36 LCM = 2³ × 3² × 5 × 7 = 8 × 9 × 5 × 7 = LCM = 2,520