Veröffentlicht · wird verbessert
Mathematik und Zahlentheorie-Anleitung · 3/6
Dieses Kapitel ist vorerst nur auf Englisch verfügbar.
This chapter builds the sieve, extended Euclid, the modular inverse and fast exponentiation as one Python module, explains it line by line, then ports the sieve to C++, Java and TypeScript.
def sieve(n: int) -> list[int]:
"""Return all primes <= n in ascending order."""
if n < 2:
return []
is_prime = bytearray([1]) * (n + 1)
is_prime[0] = is_prime[1] = 0
i = 2
while i * i <= n:
if is_prime[i]:
count = (n - i * i) // i + 1
is_prime[i * i :: i] = bytes(count)
i += 1
return [k for k in range(n + 1) if is_prime[k]]
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""Return (g, x, y) with a * x + b * y == g == gcd(a, b)."""
old_r, r = a, b
old_x, x = 1, 0
old_y, y = 0, 1
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
def mod_inverse(a: int, m: int) -> int:
"""Return x in [0, m) with a * x % m == 1; raise ValueError if none exists."""
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError(f"{a} has no inverse modulo {m}")
return x % m
def mod_pow(base: int, exp: int, mod: int) -> int:
"""Compute base ** exp % mod with O(log exp) multiplications."""
result = 1 % mod
base %= mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
if __name__ == "__main__":
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(extended_gcd(240, 46)) # (2, -9, 47)
print(mod_inverse(3, 7)) # 5
print(mod_pow(3, 13, 7)) # 3
print(mod_pow(2, 10**18, 10**9 + 7) == pow(2, 10**18, 10**9 + 7)) # Truesieve
bytearray([1]) * (n + 1) uses one byte per slot; a [True] * (n + 1) list stores an 8-byte pointer per slot.i * i > n: every composite has a prime factor no larger than its square root, so the rest are already crossed out.is_prime[i * i :: i] = bytes(count) zeroes every i-th slot from i × i in one slice assignment, much faster than a Python loop. count must equal the slice length.extended_gcd
(old_r, r) are the two remainders; (old_x, x) and (old_y, y) write each remainder as a × x + b × y, starting from a = a × 1 + b × 0 and b = a × 0 + b × 1.new = previous - q × currentmod_inverse
a % m first handles negative a.g != 1 there is no inverse, so it raises instead of returning a wrong value.x % m normalizes a negative x into [0, m).mod_pow
result = 1 % mod makes the answer 0 when mod == 1.exp & 1 inspects the lowest bit; if it is 1, the current base is multiplied into the result.base and shifting exp right by one moves on to the next bit.% mod on every step keeps them small. In production, the built-in pow(base, exp, mod) is fastest.vector<bool> is bit-packed, and long long keeps i * i from overflowing int.
#include <iostream>
#include <vector>
std::vector<int> sieve(int n) {
std::vector<int> primes;
if (n < 2) return primes;
std::vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (long long i = 2; i * i <= n; ++i) {
if (!is_prime[i]) continue;
for (long long j = i * i; j <= n; j += i) is_prime[j] = false;
}
for (int k = 2; k <= n; ++k)
if (is_prime[k]) primes.push_back(k);
return primes;
}
int main() {
for (int p : sieve(30)) std::cout << p << ' ';
std::cout << '\n'; // 2 3 5 7 11 13 17 19 23 29
}A boolean[] starts all false, so storing "is composite" skips initialization; long avoids overflow in i * i.
import java.util.ArrayList;
import java.util.List;
public class Sieve {
static List<Integer> sieve(int n) {
List<Integer> primes = new ArrayList<>();
if (n < 2) return primes;
boolean[] composite = new boolean[n + 1];
for (long i = 2; i * i <= n; i++) {
if (composite[(int) i]) continue;
for (long j = i * i; j <= n; j += i) composite[(int) j] = true;
}
for (int k = 2; k <= n; k++)
if (!composite[k]) primes.add(k);
return primes;
}
public static void main(String[] args) {
System.out.println(sieve(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
}
}A Uint8Array uses one byte per slot, and number is exact up to 2^53, so the index arithmetic is safe.
export function sieve(n: number): number[] {
if (n < 2) return [];
const isPrime = new Uint8Array(n + 1).fill(1);
isPrime[0] = 0;
isPrime[1] = 0;
for (let i = 2; i * i <= n; i++) {
if (!isPrime[i]) continue;
for (let j = i * i; j <= n; j += i) isPrime[j] = 0;
}
const primes: number[] = [];
for (let k = 2; k <= n; k++) if (isPrime[k]) primes.push(k);
return primes;
}
console.log(sieve(30).join(" ")); // 2 3 5 7 11 13 17 19 23 29All four sieves share the same shape: clear 0 and 1, cross out multiples from i × i for every prime i with i × i ≤ n, and collect what is left. They differ only in memory representation (bytearray, vector<bool>, boolean[], Uint8Array) and in how they keep i × i from overflowing. Extended Euclid and fast exponentiation need care with multiplication overflow in C++ and Java; see the real-world chapter.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.