Prime Numbers

Definition and first examples

A prime number is an integer 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, 31, 37, 41, 43, 47, ...

Numbers greater than 1 that aren't prime are composite — they have factorizations into smaller integers. 4 = 2×2, 6 = 2×3, 8 = 2×2×2, 9 = 3×3, etc.

The number 1 is neither prime nor composite by convention. Excluding 1 from primes keeps the Fundamental Theorem of Arithmetic clean — every integer > 1 has a unique prime factorization (without the "and you can throw in any number of 1s" caveat).

Fundamental Theorem of Arithmetic

Every positive integer greater than 1 can be written as a product of primes in exactly one way (up to order). For example:

12 = 2 · 2 · 3 = 2² · 3
60 = 2² · 3 · 5
1024 = 2¹⁰
2024 = 2³ · 11 · 23

Two implications:

• Primes are the "atoms" of arithmetic — every integer is built from them by multiplication.
• The factorization is unique — no integer has two essentially different prime factorizations.

There are infinitely many primes (Euclid)

Suppose there were only finitely many primes p₁, p₂, ..., pₙ. Consider N = p₁ · p₂ · ... · pₙ + 1. Either N is prime (and not in our list — contradiction) or it's divisible by some prime not in our list (because dividing N by any pᵢ leaves remainder 1). Either way, our supposed-finite list was incomplete. So primes are infinite. Euclid (~300 BCE).

Prime Number Theorem — how many primes

The number of primes ≤ n, denoted π(n), grows like:

π(n) ≈ n / ln(n)

n	π(n) actual	n / ln(n)	Ratio
10	4	4.34	0.92
100	25	21.7	1.15
1,000	168	144.8	1.16
10,000	1,229	1,085.7	1.13
10⁶	78,498	72,382	1.08
10⁹	50,847,534	48,254,942	1.054

The ratio approaches 1 as n grows — that's the Prime Number Theorem. Among the first n integers, roughly n/ln(n) are prime. For n = 1 billion, about 5% are prime; for n = 1 trillion, about 3%; for n = 10⁵⁰, vanishingly few.

Finding primes — the Sieve of Eratosthenes

To find all primes ≤ N:

1. List integers 2, 3, 4, ..., N.
2. Find the smallest unmarked number (initially 2). It's prime; mark all its multiples (4, 6, 8, ...) as composite.
3. Repeat — find next unmarked, mark its multiples (skipping already-marked).
4. Stop when you reach √N. All remaining unmarked numbers are prime.

Time complexity O(N log log N). For finding primes up to 10⁹, this is fast on modern hardware (a few seconds). For larger ranges, segmented sieves and probabilistic tests (Miller-Rabin) are used.

JavaScript — Sieve of Eratosthenes

function sieveOfEratosthenes(N) {
  const sieve = new Uint8Array(N + 1);  // 0 = unmarked (prime), 1 = composite
  sieve[0] = sieve[1] = 1;
  for (let i = 2; i * i <= N; i++) {
    if (!sieve[i]) {
      for (let j = i * i; j <= N; j += i) sieve[j] = 1;
    }
  }
  const primes = [];
  for (let i = 2; i <= N; i++) if (!sieve[i]) primes.push(i);
  return primes;
}

console.log(sieveOfEratosthenes(50));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

// Quick primality test (trial division — for small n)
function isPrime(n) {
  if (n < 2) return false;
  if (n < 4) return true;
  if (n % 2 === 0) return false;
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}

// Miller-Rabin test for large numbers (probabilistic, very fast)
function millerRabin(n, k = 5) {
  if (n < 2) return false;
  if (n < 4) return true;
  if (n % 2 === 0) return false;

  let d = n - 1, r = 0;
  while (d % 2 === 0) { d /= 2; r++; }

  WitnessLoop: for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (n - 4));
    let x = modPow(a, d, n);
    if (x === 1 || x === n - 1) continue;
    for (let j = 0; j < r - 1; j++) {
      x = (x * x) % n;
      if (x === n - 1) continue WitnessLoop;
    }
    return false;
  }
  return true;
}
function modPow(base, exp, mod) {
  let result = 1;
  base %= mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}

Special prime types

Type	Form	Examples	Notable
Mersenne	2^p − 1 where p prime	3, 7, 31, 127, 8191	Largest known primes are Mersenne
Fermat	2^(2^n) + 1	3, 5, 17, 257, 65537	Only 5 are currently known prime
Twin primes	(p, p+2) both prime	(3,5), (5,7), (11,13), (17,19)	Twin Prime Conjecture — infinite many?
Sophie Germain	p prime, 2p+1 also prime	2, 3, 5, 11, 23, 29	Used in cryptography
Cousin primes	(p, p+4) both prime	(3,7), (7,11), (13,17)	Less famous than twins
Sexy primes	(p, p+6) both prime	(5,11), (7,13), (11,17)	Yes, that's the actual name

Primes in cryptography

RSA, the most widely-used public-key cryptosystem, depends on the difficulty of factoring large numbers into primes. The procedure:

1. Pick two large primes p and q (each typically 1024 bits, so 2048-bit RSA).
2. Compute n = p · q.
3. Compute φ(n) = (p − 1)(q − 1) (Euler's totient function).
4. Pick e coprime with φ(n) (commonly 65537).
5. Compute d = e⁻¹ mod φ(n) (the modular inverse).
6. Public key — (n, e). Private key — (n, d).

Encryption — c = m^e mod n. Decryption — m = c^d mod n. The math relies on Euler's theorem and the difficulty of factoring n. Quantum computers (Shor's algorithm) would break this in polynomial time; classical computers can't factor 2048-bit RSA in reasonable time.

Where primes appear

• Cryptography. RSA, Diffie-Hellman, Elliptic Curve Cryptography — all build on prime-related hardness assumptions.
• Hash functions. Some hash functions use primes for table sizes (modulo prime gives better distribution than modulo composite). Universal hashing uses prime moduli explicitly.
• Coding theory. Reed-Solomon and BCH codes work over finite fields of prime order — the field axioms require prime characteristic.
• Random number generation. Linear congruential generators use prime moduli for full-period sequences. Mersenne Twister uses Mersenne primes.
• Algorithms. Many algorithms (segment trees, bit manipulation) use prime sizes for collision-free indexing.
• Mathematics — algebraic structures. Modular arithmetic mod prime gives a field; mod composite gives only a ring (not all elements have inverses). Galois fields, finite fields, group theory all build on prime-related concepts.

Common mistakes

• Including 1 as prime. By modern convention, 1 is not prime — to keep unique factorization clean. Old textbooks vary; modern math doesn't.
• Trial division to N instead of √N. For primality testing, you only need to check divisors up to √n — if n = ab with both a, b > √n, then ab > n, contradiction. Halves to quarters of the work.
• Believing primes "thin out fast." They thin out, but slowly. Even at 10²⁰⁰, ~1 in 460 numbers is prime. RSA finds 1024-bit primes by random search in milliseconds.
• Trying to test primality by listing all factorizations. Slow and unnecessary. Trial division (for small n) or Miller-Rabin (for large n) are far more efficient.
• Confusing relatively prime with prime. "Relatively prime" or "coprime" means two numbers share no common factor (gcd = 1). Either or both can be composite — 9 and 16 are coprime but neither is prime.
• Assuming the Twin Prime Conjecture is proven. It's not. We know primes are infinite (Euclid). We conjecture twin primes (p, p+2) are infinite — proven for primes ≤ ~70-million-gap (Zhang 2013), not the full conjecture.