01
What is a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, 13... All primes except 2 are odd. Primes are the "atoms of numbers."
Prime Number Calculator
Primality Test · Factorization · Prime Generation
Learn more
02
Sieve of Eratosthenes
An ancient algorithm developed by Greek mathematician Eratosthenes around 240 BC. It efficiently finds all primes up to n by iteratively marking multiples of each prime as composite.
03
Twin Primes
Twin primes are pairs of primes that differ by 2: (3,5), (5,7), (11,13), (17,19)... Whether infinitely many twin primes exist remains an unsolved problem.
04
Applications of Primes
• RSA encryption: Security based on difficulty of factoring large numbers • Hash functions: Prime-sized hash tables reduce collisions • Random number generation: Primes in PRNG algorithms • Nature: Cicada life cycles use prime numbers
05
Definition and History of Prime Numbers
A prime number is a natural number greater than 1 with no divisors except 1 and itself. The smallest prime is 2, the only even prime. Sequence: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Ancient Greek mathematician Euclid proved around 300 BC that infinitely many primes exist. Primes are called "atoms of numbers" because every integer > 1 uniquely factors into primes (Fundamental Theorem of Arithmetic). Examples: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
06
Primality Testing Algorithms
The simplest method tests divisibility by all numbers from 2 to n-1, but this is inefficient. An improvement tests only 2 to √n, since if n = a × b, then a ≤ √n or b ≤ √n. For 101: √101 ≈ 10.05, so test only 2, 3, 5, 7. Miller-Rabin probabilistic test handles very large numbers efficiently. AKS (2002) is the first polynomial-time deterministic algorithm. Modern cryptography uses hundreds of digits, requiring efficient testing.
07
Sieve of Eratosthenes Algorithm
Developed by Greek mathematician Eratosthenes around 240 BC. Process: ① List numbers 2 to n. ② Mark 2 as prime, eliminate multiples (4,6,8,10...). ③ Next unmarked number 3 is prime, eliminate multiples. ④ Continue with 5, 7, etc. up to √n. ⑤ Remaining numbers are prime. For n=30: primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Time complexity: O(n log log n). Can find all primes under 1 million in seconds.
08
Prime Factorization Principles
Prime factorization expresses a number as a product of primes. By Fundamental Theorem, every integer > 1 has a unique factorization. Method: ① Start with smallest prime 2. ② Divide repeatedly by 2 until no longer divisible. ③ Try next primes 3, 5, 7... ④ Continue until quotient is 1. Example 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Result: 360 = 2³×3²×5. Applications: GCD/LCM calculation, fraction reduction, RSA security.
09
Twin Primes and Goldbach Conjecture
Twin primes differ by 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Twin Prime Conjecture states infinitely many exist but remains unproven. In 2013, Yitang Zhang proved infinitely many prime pairs differ by ≤70 million, later reduced to 246. Goldbach Conjecture (1742): every even number > 2 is sum of two primes. Examples: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Verified up to 4×10¹⁸ but still unproven.
10
RSA Encryption and Practical Applications
RSA encryption, core of internet security, relies on easy multiplication but hard factorization of large primes. Key generation: ① Choose large primes p, q (1024+ bits each). ② Calculate n = p×q (public). ③ Calculate φ(n) = (p-1)(q-1). ④ Choose public exponent e coprime to φ(n) (usually 65537). ⑤ Calculate private exponent d where e×d ≡ 1 (mod φ(n)). Public key: (n,e), private key: (n,d). Encrypt: C = M^e mod n, Decrypt: M = C^d mod n. Factoring n to find p,q would break encryption, but factoring hundreds of digits takes millions of years. Other applications: prime hash table sizes reduce collisions, cicada 13/17-year cycles avoid predator overlap, prime rhythms in music.
Frequently asked questions
What is the range I can test?
This tool supports primality testing and factorization for numbers from 1 to 10,000,000, while prime generation and twin-prime finding work in the 2–100,000 range.
Why are primes used in cryptography?
Multiplying two large primes is easy, but factoring the product back into those primes is extremely hard. RSA encryption exploits exactly this asymmetry to protect internet communication.