EMZETT.
Login

Emzett Wiki

Prime numbers and the Sieve of Eratosthenes: calculating with divisibility

Properties1
tagsglossar, mathematik, algorithmen

3 min read

Prime numbers and the Sieve of Eratosthenes: calculating with divisibility

In short: Primes are divisible only by 1 and themselves; with the Sieve of Eratosthenes you find all up to n quickly, and their difficulty to factorise secures encryption such as RSA.

In more detail: A prime number is a natural number > 1 with exactly two divisors (1 and itself): 2, 3, 5, 7, 11, 13 … Every number can be decomposed uniquely into prime factors (fundamental theorem of arithmetic): 360 = 2³ · 3² · 5.

In Depth

Primality test

Naive: n is prime if no divisor exists from 2 to √n (larger divisors would have a small partner):

def is_prime(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0: return False
        i += 2
    return True

Running time O(√n). For huge numbers (RSA, 2048 bit) one uses probabilistic tests (Miller-Rabin) and AKS (deterministic, polynomial, but slow).

Sieve of Eratosthenes

All primes up to n: list 2..n, then cross out the multiples of each prime found.

def sieve(n):
    is_p = [True] * (n + 1); is_p[0:2] = [False, False]
    for p in range(2, int(n ** 0.5) + 1):
        if is_p[p]:
            for k in range(p * p, n + 1, p):
                is_p[k] = False
    return [i for i, b in enumerate(is_p) if b]

Example sieve(30) → 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Effort O(n log log n), memory O(n) (bit array saves space). Cross out from p², because smaller multiples were already crossed out by smaller primes.

Important terms

  • Divisibility rules: by 2 (even), 3 (digit sum), 5 (last digit 0/5), 9, 11 (alternating digit sum).
  • gcd/lcm: Euclid; lcm = a·b / gcd.
  • Modulo (%) and residue classes: clock arithmetic, hash functions, check digits (IBAN, ISBN), cycles.
  • Prime factorisation: gcd/lcm, reducing fractions.
  • Mersenne primes 2^p − 1 (largest known primes), twin primes (11/13), Goldbach conjecture (unsolved).
  • Density: number of primes ≤ n ≈ n / ln n.

Why primes matter in IT

  • RSA: two large primes p, q are multiplied (n = p·q public); factoring n is hard, that carries the security. A quantum computer (Shor’s algorithm) could break this → post-quantum cryptography.
  • Diffie-Hellman, elliptic curves: modular arithmetic over prime fields.
  • Hash tables: size often prime (better spreading).
  • Random number generators, checksums.
  • Key generation: prime search with Miller-Rabin (OpenSSL).
  • Exam (IHK): divisibility, modulo, simple programs.

See also: Euclidean algorithm, Big-O notation, Hashmap

Backlinks