Prime Number Calculator
Check primality, compute prime factorization, and find all primes within a number range.
Reviewed by CalculatorApp.me Math Team
Prime Number Calculator — Complete Guide
Primality testing, factorization, sieves, and the role of primes in cryptography and mathematics.
168
Primes below 1000
2
Only even prime
∞
Infinitely many primes
RSA
Crypto uses primes
What Are Prime Numbers?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Prime numbers are the "atoms" of arithmetic — every integer greater than 1 can be uniquely expressed as a product of primes (the Fundamental Theorem of Arithmetic).
Composite numbers have additional factors: 12 = 2² × 3, 100 = 2² × 5². The number 1 is neither prime nor composite by modern convention. The number 2 is the only even prime — all other even numbers are divisible by 2.
Primes are central to modern cryptography: RSA encryption relies on the fact that multiplying two large primes is easy, but factoring their product is computationally infeasible. A 2048-bit RSA key uses primes with ~300 digits each. This asymmetry secures online banking, HTTPS, and digital signatures worldwide.
Primality Testing Methods
Algorithm: Test divisibility by all
integers from 2 to √n
def is_prime(n):
if n < 2: return False
if n < 4: return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i+2) == 0:
return False
i += 6
return True
Why only test up to √n?
If n = a × b, then min(a,b) ≤ √n
So if no factor ≤ √n, n is prime
Complexity: O(√n)
For n = 1,000,000 → test ~1000 values
Practical for n up to ~10¹²Trial division is the simplest primality test. The optimization of testing only 6k±1 (skipping multiples of 2 and 3) reduces checks by 67%. Sufficient for everyday use.
Find ALL primes up to N: 1. List numbers 2, 3, 4, ..., N 2. Start with smallest (2) 3. Mark all multiples of 2 as composite 4. Move to next unmarked number (3) 5. Mark all multiples of 3 6. Repeat until √N reached 7. Remaining unmarked = PRIMES Sieve of Eratosthenes (up to 30): 2 3 4̶ 5 6̶ 7 8̶ 9̶ 10̶ 11 12̶ 13 14̶ 15̶ 16̶ 17 18̶ 19 20̶ 21̶ 22̶ 23 24̶ 25̶ 26̶ 27̶ 28̶ 29 30̶ Primes: 2,3,5,7,11,13,17,19,23,29 Complexity: O(n log log n) Memory: O(n) → segmented for large n
The Sieve of Eratosthenes (240 BC) is still one of the fastest algorithms for generating all primes up to N. For primes below 10⁹, segmented sieves run in seconds on modern hardware.
Probabilistic primality test:
'Probably prime' or 'definitely composite'
Basis: Fermat's Little Theorem
If p is prime: a^(p-1) ≡ 1 (mod p)
Miller-Rabin extends this:
Write n−1 = 2ˢ × d (d odd)
Choose random witness a
Compute a^d mod n
If = 1 or n−1: probably prime
Square up to s−1 times:
If any = n−1: probably prime
Otherwise: COMPOSITE (certain)
Error probability: ≤ (1/4)^k
k witnesses → P(error) ≤ 4⁻ᵏ
20 witnesses → P(error) < 10⁻¹²
Deterministic variant:
Test a = 2,3,5,7,11,13,17,19,23,29,31,37
Correct for all n < 3.317×10²⁴Miller-Rabin is the standard primality test in practice. With enough witnesses, false positives are astronomically unlikely. Most crypto libraries use Miller-Rabin with 40+ rounds for key generation.
Express n as product of primes:
Trial Division Factorization:
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 2³ × 3² × 5
Applications:
GCD(a,b): min of each prime power
LCM(a,b): max of each prime power
GCD(12,18) = GCD(2²×3, 2×3²)
= 2¹×3¹ = 6
LCM(12,18) = 2²×3² = 36
Number of divisors:
n = p₁^a₁ × p₂^a₂ × ...
d(n) = (a₁+1)(a₂+1)...
360 = 2³×3²×5¹
d(360) = 4×3×2 = 24 divisors
Cryptographic factoring:
RSA-2048: ~617 digit number
No known efficient algorithm!Factoring large numbers is computationally hard — this is the foundation of RSA encryption. If quantum computers achieve sufficient scale, Shor's algorithm could factor in polynomial time, breaking RSA.
Special Types of Primes
| Type | Form | Examples | Known Count | Significance |
|---|---|---|---|---|
| Mersenne | 2ᵖ − 1 | 3, 7, 31, 127 | 51 known | Largest known primes |
| Twin | p, p+2 | (3,5), (11,13), (41,43) | ∞ conjectured | Twin prime conjecture |
| Sophie Germain | p & 2p+1 prime | 2, 3, 5, 11, 23 | ∞ conjectured | Cryptographic use |
| Fermat | 2^(2ⁿ)+1 | 3, 5, 17, 257, 65537 | 5 confirmed | Constructible polygons |
| Palindromic | Reads same both ways | 11, 101, 131, 151 | ∞ conjectured | Recreational math |
| Safe | (p−1)/2 is prime | 5, 7, 11, 23, 47 | ∞ conjectured | Strong crypto keys |
| Emirp | Prime reversed too | 13↔31, 17↔71 | ∞ conjectured | Number theory |
| Gaussian | a+bi, irreducible | 3, 7, 11, 2+i | ∞ | Complex primes |
Prime Distribution
| Range | Prime Count | Density | Largest Prime in Range |
|---|---|---|---|
| 1 – 100 | 25 | 25% | 97 |
| 1 – 1,000 | 168 | 16.8% | 997 |
| 1 – 10,000 | 1,229 | 12.3% | 9,973 |
| 1 – 100,000 | 9,592 | 9.6% | 99,991 |
| 1 – 1,000,000 | 78,498 | 7.8% | 999,983 |
| 1 – 10⁹ | 50,847,534 | 5.1% | 999,999,937 |
| 1 – 10¹² | 37,607,912,018 | 3.8% | 999,999,999,989 |
Density decreases logarithmically: π(x) ≈ x/ln(x) (Prime Number Theorem). Primes never run out, but they thin out at a predictable rate.
History of Prime Numbers
Euclid — Infinitely Many Primes
In Elements (Book IX, Prop. 20), Euclid proved there are infinitely many primes with an elegant contradiction argument still taught today: assume finitely many, multiply them all and add 1 — the result is not divisible by any known prime. Therefore another prime must exist.
Eratosthenes — The First Prime Sieve
Eratosthenes of Cyrene created the first systematic algorithm for finding primes. His sieve method — crossing out multiples of each prime starting from 2 — remains one of the most efficient algorithms for generating all primes up to N. Still used in competitive programming 2,300 years later.
Fermat — Fermat's Little Theorem
Pierre de Fermat stated (without proof) that if p is prime, then aᵖ⁻¹ ≡ 1 (mod p). Euler later proved it. This theorem became the basis for probabilistic primality tests (Fermat test, Miller-Rabin) still used in modern cryptography.
Gauss & Legendre — Prime Number Theorem Conjecture
Both Gauss and Legendre independently conjectured that π(x) ≈ x/ln(x) — the number of primes below x grows inversely with the natural logarithm. This was proved rigorously in 1896 by Hadamard and de la Vallée-Poussin using complex analysis.
RSA — Primes Secure the Internet
Rivest, Shamir, and Adleman published the RSA cryptosystem, which relies on the difficulty of factoring products of large primes. If n = p × q with ~300-digit primes, finding p and q from n is computationally infeasible. RSA secures nearly all internet communication.
Largest Known Prime: 2⁸²,⁵⁸⁹,⁹³³ − 1
The largest known prime as of 2024 has 24,862,048 digits — discovered by the Great Internet Mersenne Prime Search (GIMPS). It would take ~8,800 pages to print. The search for large primes continues as both mathematical pursuit and distributed computing project.
Key Research & Data
Rivest, Shamir, Adleman (1978) — CACM
RSA: Primes Secure Digital Communication
RSA encryption depends on the computational asymmetry of primes: multiplying two 1024-bit primes takes microseconds, but factoring their 2048-bit product would take millions of years with current technology. This secures HTTPS, banking, and digital signatures globally.
Hadamard & de la Vallée-Poussin (1896)
Prime Number Theorem — Proved
Independently proved that π(n) ~ n/ln(n): the number of primes up to n approaches n divided by the natural logarithm of n. This confirmed Gauss's conjecture and established the logarithmic thinning of primes as absolute mathematical fact.
Yitang Zhang (2013) — Annals of Mathematics
Bounded Gaps Between Primes
Proved that there are infinitely many pairs of primes differing by at most 70 million — the first finite bound on prime gaps. The Polymath project reduced this to 246. The twin prime conjecture (gap = 2) remains unproven but Zhang's breakthrough was historic.
GIMPS — Great Internet Mersenne Prime Search
Distributed Computing Finds Largest Primes
Since 1996, the GIMPS project uses volunteers' computers to search for Mersenne primes (2ᵖ−1). It has found the 17 largest known primes, including the current record-holder with 24.8 million digits. Anyone with a computer can contribute to this mathematical frontier.
Myths vs. Facts
There is a formula that generates all prime numbers.
No known formula efficiently generates all primes. While formulas exist (like Wilson's theorem: p is prime iff (p−1)!+1 divisible by p), they're computationally useless. The distribution of primes follows patterns (PNT) but individual primes appear unpredictably.
1 is a prime number.
By modern convention (established ~1900s), 1 is NOT prime. If 1 were prime, the Fundamental Theorem of Arithmetic would fail — factorizations wouldn't be unique (12 = 2²×3 = 1×2²×3 = 1²×2²×3...). Excluding 1 preserves unique factorization.
Larger numbers are less likely to be prime, so primes eventually run out.
Primes thin out (density ≈ 1/ln(n)) but NEVER stop. Euclid proved infinitely many primes exist ~300 BC. No matter how large a number you pick, there's always another prime beyond it. The thinning is logarithmic, not finite.
Quantum computers will immediately break all encryption.
Shor's algorithm can theoretically factor large numbers in polynomial time, threatening RSA. But current quantum computers have ~1,000 qubits; breaking RSA-2048 requires millions of error-corrected qubits. Post-quantum cryptography (lattice-based) is already being deployed as a precaution.
Frequently Asked Questions
How do I check if a number is prime?▼
What are the factors of a number, like 40, 27, or 50?▼
Why is 2 the only even prime?▼
What is the Fundamental Theorem of Arithmetic?▼
What are twin primes?▼
How does RSA encryption use primes?▼
What is the largest known prime number?▼
What is the Sieve of Eratosthenes?▼
Do primes follow a pattern?▼
What is the Goldbach Conjecture?▼
What are Mersenne primes?▼
What is a prime factorization tree?▼
References
- Rivest, Shamir, Adleman — A Method for Obtaining Digital Signatures (1978)
- Yitang Zhang — Bounded Gaps Between Primes (2014)
- Great Internet Mersenne Prime Search (GIMPS)
- Crandall & Pomerance — Prime Numbers: A Computational Perspective
- Clay Mathematics Institute — Riemann Hypothesis
- Wolfram MathWorld — Prime Number Theorem
Related Calculators
Explore All Math Calculators
Precision math tools for students, cryptographers, and number theorists — CalculatorApp.me.
Browse Math Calculators →Prime Number Calculator — Answer & Method
Check if a number is prime, find prime factors, and generate lists of prime numbers.
Formula: Prime Test
Check divisibility for all primes ≤ √n
Example Calculation
97 is prime — it has no divisors other than 1 and itself.
Important limitation
Check the result against your specific circumstances before making a decision.
Key Facts
- A prime number has exactly two distinct positive divisors: 1 and itself.
- 2 is the only even prime number.