リリース・改善中
数学と整数論 ガイド · 3/6
この章は現在、英語でのみ提供しています。
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件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。