Util Monster
Primality Test · Factorization · Prime Generation
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."
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.
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.
• 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
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.
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.
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.
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.
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.
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.