Loading page content...
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
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 percentage calculations with this comprehensive guide covering percentage formulas, increase/decrease, percentage of a number, reverse percentages, and common real-world applications.
Complete geometry reference covering area formulas, volume calculations, triangles, circles, and 3D shapes. Free area calculator, volume calculator, and right triangle solver included.
Complete GPA guide covering weighted vs. unweighted GPA, cumulative GPA calculation, grade conversion charts, and strategies to raise your GPA. Free GPA and grade calculators included.
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.
| 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 |
| 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Ā¹Ā² |
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, 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
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.
Fraction Calculator
GCD & LCM from prime factors
Binary Calculator
Binary representations of primes
Exponent Calculator
Powers in Mersenne primes
Probability Calculator
Prime distribution probability
Logarithm Calculator
ln(x) in prime counting theorem
Equation Solver
Solve prime-related equations
Precision math tools for students, cryptographers, and number theorists ā CalculatorApp.me.
Browse Math Calculators āLast updated:
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.
| ā 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 |
| 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.
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.
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.
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.