Loading page content...
Last updated:
Reviewed by CalculatorApp.me Math Team
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
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.
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.
| 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 |
| 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.
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 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.
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.
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.
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.
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.
Rivest, Shamir, Adleman (1978) — CACM
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)
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
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
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.
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.
Precision math tools for students, cryptographers, and number theorists — CalculatorApp.me.
Browse Math Calculators →Free online prime number calculator — check primality, find prime factors, and list primes in any range with AI-powered insights.
Enter values above to see results.
Explore our in-depth guides related to this calculator
Master every percentage calculation in 2026: the 4 core formulas, percentage increase/decrease, reverse percentage, CAGR, markup vs. margin, tip/tax/discount math, GPA percentages, statistics (percentile, z-score), and compounding — with 15 long-tail keyword examples and a free percentage calculator.
Complete 2026 geometry reference covering 2D area formulas, 3D volume and surface area calculations, triangles, circles, coordinate geometry, and composite shapes. Includes free area calculator, volume calculator, surface area calculator, and right triangle solver. NIST-aligned, with 25+ shapes, 40+ formulas, and real-world applications for flooring, landscaping, construction, and engineering.
Complete GPA calculator guide 2026: step-by-step weighted and unweighted GPA formulas, cumulative GPA tracking, grade conversion charts, medical/law/grad school GPA requirements, and proven strategies to raise your GPA fast. Covers plus/minus grading, grade replacement policies, honors thresholds, and what-if semester modeling. Free calculators included.