Prime Number Checker

The √n bound makes primality testing efficient:

• ›Mathematical proof, suppose n = a × b where a > √n. Then b = n/a < n/√n = √n. So b < √n, meaning b would have been found before a in our test.
• ›Practical impact, for n = 1,000,000,000 (1 billion), we only need to test up to √(10⁹) ≈ 31,623. That is only 31,623 divisions instead of nearly a billion.
• ›Further optimization, testing 6k±1 (i.e., 5, 7, 11, 13, 17, 19, …) skips all multiples of 2 and 3 first, cutting the work by ⅔ before we even start the loop.
• ›Performance, this calculator handles numbers up to 1 billion near-instantly because trial division up to ~31,623 is trivial for modern hardware.

Twin primes are among the most studied structures in number theory:

• ›Definition, a pair (p, p+2) where both p and p+2 are prime. The smallest twin prime pair is (3, 5).
• ›Examples, (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73).
• ›Twin Prime Conjecture, believed to be true but unproven. Yitang Zhang's landmark 2013 paper proved infinitely many prime pairs with gap ≤ 70,000,000, since narrowed to 246 by the Polymath project.
• ›Density, twin primes become rarer as numbers grow, but appear to continue infinitely. The density near n is approximately 2C₂ / (ln n)² where C₂ ≈ 0.6601618 is the twin prime constant.

Mersenne primes are rare and computationally significant:

• ›Form, Mₖ = 2ᵏ − 1. For Mₖ to be prime, k itself must be prime (though prime k does not guarantee Mₖ is prime, e.g., 2¹¹−1 = 2047 = 23 × 89).
• ›Known examples, 3, 7, 31, 127, 8191, 131071, 524287, … The 51st known Mersenne prime (found 2024) has over 41 million digits.
• ›GIMPS, the Great Internet Mersenne Prime Search is a distributed computing project that has found all recent record primes since 1996.
• ›Connection to perfect numbers, every Mersenne prime Mₖ generates an even perfect number: 2^(k-1) × Mₖ. For example, M₂ = 3 gives the perfect number 2¹ × 3 = 6.

Euclid's proof of the infinitude of primes is one of the oldest and most elegant in mathematics:

• ›The proof, assume primes are finite: p₁, p₂, …, pₙ. Let N = p₁×p₂×⋯×pₙ + 1. Then N mod pᵢ = 1 for every prime in our list, so no listed prime divides N.
• ›Conclusion, N is either prime itself or has a prime factor not in our list. Either way, the list was not complete. Contradiction, so there cannot be a finite list of all primes.
• ›Prime counting function, π(n) counts primes up to n. The Prime Number Theorem says π(n) ≈ n/ln(n). There are 78,498 primes below 1,000,000 and about 50,847,534 below 10⁹.
• ›Unsolved questions, whether infinitely many twin primes, Sophie Germain primes, and Mersenne primes exist all remain open conjectures despite the infinity of ordinary primes.

Safe primes have both mathematical and cryptographic significance:

• ›Definition, a prime p where (p−1)/2 is also prime. The linked pair: (p−1)/2 is the Sophie Germain prime; p is the safe prime.
• ›Examples, 11 (Sophie: 5), 23 (11), 47 (23), 59 (29), 83 (41), 107 (53), 167 (83), 179 (89).
• ›Cryptography, safe primes are ideal for Diffie–Hellman key exchange because the multiplicative group mod p has only trivial small subgroups (order 1, 2, and (p−1)/2). This prevents small subgroup attacks.
• ›Rarity, safe primes become increasingly sparse as numbers grow, though infinitely many are conjectured to exist (unproven).

Prime gaps measure the spacing between consecutive primes:

• ›Definition, if p and q are consecutive primes (q is the next prime after p), the prime gap is q − p.
• ›Small gaps, gap of 1 only for (2,3). Gap of 2 for twin primes like (5,7), (11,13), (17,19). The smallest gap for primes > 2 is 2.
• ›Large gaps, for any k, we can find k consecutive composites: (k+1)! + 2, (k+1)! + 3, …, (k+1)! + (k+1) are all composite. So gaps can be as large as desired.
• ›Average gap, the Prime Number Theorem tells us primes near n have average spacing ≈ ln(n). Near 1,000,000 the average gap is ≈ ln(10⁶) ≈ 13.8.

Primes are the mathematical foundation of internet security:

• ›RSA encryption, the public key is n = p × q for two large secret primes. Encryption and decryption use modular arithmetic with n. Security depends on factoring n being computationally intractable.
• ›Factoring hardness, the best classical algorithms (GNFS) can factor a 768-bit number in about a year of supercomputer time. RSA-2048 is considered secure beyond 2040.
• ›Diffie-Hellman, uses a large prime p and a generator g to enable two parties to establish a shared secret over a public channel without exchanging the secret directly.
• ›Quantum threat, Shor's algorithm runs on a quantum computer and factors n in polynomial time. Post-quantum cryptography standards (NIST PQC, 2024) are being deployed to replace RSA before large quantum computers exist.