Prime Number Checker
Check if a number is prime and find its factors. Use this free prime checker to instantly test any number and find all prime factors. No signup needed.
What is a Prime Number?
A prime number is a natural number greater than 1 that has exactly two distinct factors: 1 and itself. The first primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...
Key facts about prime numbers:
- 2 is the only even prime. Every other even number is divisible by 2, so it has more than two factors.
- 1 is not prime by modern convention. Excluding 1 preserves the uniqueness of prime factorization (Fundamental Theorem of Arithmetic).
- Primes are infinite. Euclid proved this around 300 BC: assume a finite list of all primes p₁, p₂, ..., pₙ. Then the number (p₁ × p₂ × ... × pₙ) + 1 is either prime itself or has a prime factor not in the list — contradiction. Therefore the list is infinite.
- As numbers grow larger, primes become less frequent — but they never stop. There are 25 primes below 100, 168 below 1,000, and 78,498 below 1,000,000.
A composite number is any positive integer greater than 1 that is not prime — it has at least one factor other than 1 and itself. The number 12 is composite because 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Every composite number has a unique prime factorization (Fundamental Theorem of Arithmetic).
How to Check if a Number is Prime
Several methods exist for primality testing, ranging from simple trial division to advanced probabilistic algorithms:
Trial Division (basic method): Test whether any integer from 2 to √n divides n evenly. If none do, n is prime. You only need to check up to √n because if n = a × b with a ≤ b, then a ≤ √n. If no divisor is found up to √n, there is none above √n either.
Optimized trial division: After checking divisibility by 2, only test odd numbers. Further: check 2, 3, then only numbers of the form 6k±1 (since all primes > 3 are of this form). This reduces the number of tests by about 66% compared to naïve trial division.
| Number | √n (approx) | Test divisors up to | Prime? |
|---|---|---|---|
| 97 | 9.85 | 2, 3, 5, 7 | Yes (none divide evenly) |
| 91 | 9.54 | 2, 3, 5, 7 | No (7 × 13 = 91) |
| 1,009 | 31.76 | Up to 31 | Yes (prime) |
| 1,001 | 31.64 | Up to 31 | No (7 × 11 × 13 = 1,001) |
| 7,919 | 88.99 | Up to 89 | Yes (the 1,000th prime) |
For large numbers (hundreds of digits), trial division is computationally infeasible. Advanced tests like the Miller-Rabin primality test (probabilistic, used in cryptography) and the AKS primality test (deterministic polynomial-time, 2002) are used instead.
Prime Factorization
Every composite number can be written as a unique product of primes — its prime factorization. This is guaranteed by the Fundamental Theorem of Arithmetic. To find the prime factorization, divide repeatedly by the smallest prime factor:
| Number | Prime factorization | Factor tree breakdown |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1,024 | 2¹⁰ | All prime factors are 2 |
| 2,310 | 2 × 3 × 5 × 7 × 11 | Product of first 5 primes |
Prime factorization is used to find the greatest common divisor (GCD) and least common multiple (LCM) of numbers. GCD(12, 18) = 2² × 3? No — take the minimum power of shared primes: GCD = 2¹ × 3¹ = 6. LCM takes the maximum power: LCM(12, 18) = 2² × 3² = 36.
Why Primes Matter: Applications in Mathematics and Technology
Primes are the "atoms" of arithmetic — the Fundamental Theorem of Arithmetic states that every positive integer greater than 1 is either prime or can be expressed as a unique product of primes. This uniqueness makes primes the irreducible building blocks of all numbers.
Modern internet security depends on prime numbers. RSA encryption (used for HTTPS, email encryption, and digital signatures) generates public keys by multiplying two large primes p and q to form n = p × q. Encryption and decryption keys are computed using modular arithmetic with n. The security relies on the integer factorization problem: given n (a 2048-bit number with ~617 decimal digits), finding p and q is computationally infeasible with current technology.
Diffie-Hellman key exchange uses large prime moduli for secure key agreement. When you connect to a website over HTTPS, prime numbers are silently protecting your data in real time.
Hash tables use prime-sized arrays to minimize collisions. When a hash function maps keys to bucket indices, using a prime number of buckets ensures better distribution because primes have no factors that could create systematic collision patterns.
Pseudorandom number generators (PRNGs) use prime moduli in linear congruential generators and other algorithms. The period (before repetition) of such generators often equals the prime modulus minus 1.
Special Types of Primes
Within the infinite set of primes, certain subsets have special properties or significance:
| Type | Definition | Examples |
|---|---|---|
| Twin primes | Primes differing by 2 | (3,5), (11,13), (17,19), (41,43) |
| Mersenne primes | Primes of the form 2ⁿ − 1 | 3, 7, 31, 127, 8,191 |
| Fermat primes | Primes of the form 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65,537 |
| Sophie Germain primes | p and 2p+1 are both prime | 2, 3, 5, 11, 23, 29 |
| Palindromic primes | Primes that read same forwards/backwards | 11, 101, 131, 151, 181 |
| Safe primes | Primes p where (p−1)/2 is also prime | 5, 7, 11, 23, 47, 59 |
Mersenne primes (2ⁿ − 1) are particularly important because they can be tested for primality using the efficient Lucas-Lehmer test. The GIMPS (Great Internet Mersenne Prime Search) project harnesses distributed computing worldwide to find new Mersenne primes. As of 2024, the largest known Mersenne prime is 2^136,279,841 − 1, with over 41 million decimal digits.
Twin primes (pairs differing by 2) are conjectured to be infinite (Twin Prime Conjecture), but this remains unproven — one of the most famous open problems in mathematics. In 2013, Yitang Zhang proved the weaker result that there are infinitely many prime pairs differing by at most 70 million, which was later improved to 246.
Distribution of Prime Numbers
Primes become less frequent as numbers grow larger, but their distribution follows statistical patterns described by the Prime Number Theorem:
The Prime Number Theorem (proved independently by Hadamard and de la Vallée-Poussin in 1896) states that the number of primes up to N, denoted π(N), is approximately N / ln(N) for large N:
| N | Actual π(N) | Approximate N/ln(N) | Density |
|---|---|---|---|
| 100 | 25 | 21.7 | 1 in 4 |
| 1,000 | 168 | 144.8 | 1 in 6 |
| 10,000 | 1,229 | 1,085.7 | 1 in 8 |
| 100,000 | 9,592 | 8,685.9 | 1 in 10 |
| 1,000,000 | 78,498 | 72,382.4 | 1 in 13 |
| 1,000,000,000 | 50,847,534 | 48,254,942 | 1 in 20 |
The Riemann Hypothesis — one of the Millennium Prize Problems with a $1 million reward — concerns the precise distribution of prime numbers. It conjectures that all non-trivial zeros of the Riemann zeta function have real part 1/2. This is connected to how "random" the distribution of primes appears — the hypothesis predicts optimal regularity in prime gaps.
Frequently Asked Questions
Is 1 a prime number?
No. By modern mathematical convention, 1 is neither prime nor composite. Excluding 1 from primes preserves the uniqueness of prime factorization (the Fundamental Theorem of Arithmetic) — if 1 were prime, every number would have infinitely many factorizations (e.g., 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Historically, some mathematicians did consider 1 prime, but the modern definition excludes it.
What is the largest known prime?
As of 2024, the largest known prime is 2^136,279,841 − 1 (a Mersenne prime), discovered in October 2024. It has over 41 million digits. The Great Internet Mersenne Prime Search (GIMPS) project finds most record primes using distributed computing from volunteers worldwide. These enormous primes have no practical applications — their search is purely mathematical exploration.
Are there patterns in prime numbers?
Primes appear irregular, but patterns exist. All primes > 5 end in 1, 3, 7, or 9 (never 0, 2, 4, 5, 6, 8). All primes > 3 are of the form 6k±1. Twin primes (differing by 2, like 11 and 13) appear to continue forever (unproven Twin Prime Conjecture). The Prime Number Theorem describes the statistical density of primes near N as approximately 1/ln(N).
Is 2 a prime number?
Yes, 2 is prime — and it's the only even prime. 2 has exactly two factors (1 and 2), satisfying the definition. Every other even number is divisible by 2, making it composite. The primeness of 2 is a special case that often needs to be handled separately in algorithms and proofs.
How is primality used in encryption?
RSA encryption generates a key pair by: (1) selecting two large primes p and q (each 1024+ bits), (2) computing n = p×q, (3) deriving encryption key e and decryption key d using modular arithmetic. Anyone can encrypt with n and e (public key), but only the holder of p and q (or d) can decrypt. Security relies on the computational difficulty of factoring n back into p×q.
What is the fastest way to check if a number is prime?
For small numbers (up to ~10^12): optimized trial division checking only up to √n using the 6k±1 pattern. For medium numbers: Miller-Rabin primality test with a few witnesses is probabilistic but extremely fast. For very large numbers (cryptographic sizes, 1000+ digits): probabilistic tests like Miller-Rabin with many random witnesses, or the AKS test for deterministic proof.
What is a prime gap?
A prime gap is the difference between two consecutive primes. The smallest prime gap is 1 (between 2 and 3), and all other consecutive primes have gaps of at least 2 (since one must be odd). Gaps grow slowly on average: near N, the average gap between primes is ln(N). Exceptionally large prime gaps exist — there are arbitrarily long sequences of consecutive composite numbers (n!+2, n!+3, ..., n!+n are all composite for any n).
What are the prime factors of 100?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². The prime factors of 100 are 2 and 5. This factorization explains why 100 divides evenly by 1, 2, 4, 5, 10, 20, 25, 50, and 100 — each divisor corresponds to a combination of 2⁰˒¹˒² and 5⁰˒¹˒².
What is Goldbach's conjecture?
Goldbach's conjecture (1742) states that every even integer greater than 2 can be expressed as the sum of two primes. For example: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. It has been verified computationally up to 4×10^18 but remains unproven. It is one of the oldest and most famous unsolved problems in number theory.
How many prime numbers are there?
There are infinitely many prime numbers — Euclid proved this around 300 BC. The proof by contradiction: if primes were finite, their product plus 1 would be either prime or have a prime factor not in the supposed complete list, a contradiction. While primes become less dense at larger numbers, they never stop. There are exactly 78,498 primes below 1,000,000 and 5,761,455 primes below 100,000,000.
Primes in Number Theory and Unsolved Problems
Prime numbers lie at the center of some of mathematics' most beautiful and most stubbornly unsolved problems. Understanding these open questions illuminates how much we know about primes — and how much remains mysterious despite centuries of effort.
The Riemann Hypothesis (1859): The Riemann zeta function ζ(s) = Σ(1/nˢ) connects to the distribution of primes through its zeros. The hypothesis states that all non-trivial zeros lie on the critical line Re(s) = 1/2. If true, it would provide the most precise possible description of how primes are distributed. Over 10 trillion zeros have been computed and all lie on the critical line — but no proof exists. It is a Millennium Prize Problem with a $1 million award from the Clay Mathematics Institute.
Twin Prime Conjecture: Are there infinitely many pairs of primes (p, p+2) — like (11,13), (17,19), (41,43), (101,103)? The conjecture says yes, but it remains unproven. In 2013, Yitang Zhang's breakthrough proved there are infinitely many prime pairs with a gap of at most 70 million — a first-ever finite bound. The Polymath Project subsequently reduced this bound to 246, meaning we know there are infinitely many prime pairs with gap ≤ 246. The gap of 2 remains unproven.
Goldbach's Conjecture (1742): Every even integer greater than 2 is the sum of two primes. Verified computationally up to 4 × 10^18. Every even number tried so far satisfies it — often in many ways (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). Yet no proof covers all even numbers. The "weak Goldbach conjecture" (every odd number ≥ 7 is the sum of three primes) was proved in 2013 by Harald Helfgott.
Mersenne primes and perfect numbers: A Mersenne prime is one of the form 2ⁿ − 1 (where n itself must be prime). The first few are: 3, 7, 31, 127, 8,191. Only 52 are known as of 2024. Mersenne primes are connected to perfect numbers: every Mersenne prime generates an even perfect number via the formula 2^(p−1) × (2^p − 1). The number 28 = 4 × 7 (using Mersenne prime 7) and 496 = 16 × 31 (using Mersenne prime 31) are perfect numbers. Are there infinitely many Mersenne primes? Unknown.
The ABC Conjecture and its implications: The ABC conjecture (stated in 1985) is a deep relationship about the prime factorizations of three numbers a + b = c. If proven, it would imply Fermat's Last Theorem and many other results as easy corollaries. In 2012, Shinichi Mochizuki published a claimed proof using his Inter-universal Teichmüller theory — but the proof is so novel and complex that the mathematical community has been debating its validity for over a decade, with some mathematicians accepting it and others finding a gap.
Prime numbers remain the ultimate mathematical mystery: simple to define (a number with exactly two factors), yet their distribution is complex enough to underlie open problems that have resisted the greatest mathematical minds for centuries. Every new record prime discovered, every computational verification of a conjecture to a new limit, and every partial proof advances our understanding — while reminding us how much more there is to discover.