数学と整数論

number_theory.py

import math


def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


def mod_pow(base: int, exp: int, mod: int) -> int:
    result, base = 1 % mod, base % mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result


def sieve(n: int) -> list[int]:
    is_prime = [False, False] + [True] * (n - 1)
    for i in range(2, math.isqrt(n) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]


MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36)  # 12 252
print(mod_pow(3, 200, 13))                  # 9
print(mod_pow(3, MOD - 2, MOD))             # 333333336, the inverse of 3
print(sieve(30))                            # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

python number_theory.py