(old) numtheory.py

# N linear_congruences
# I {"version": "1.0", "typing": ["Iterable"]}
def linear_congruences(a: Iterable[int], m: Iterable[int]) -> int:
    """Returns a solution of the given system of linear congruences.

    This function finds the smallest non-negative integer x that satisfies the
    following simultaneous linear congruence equations:
       x % m_0 = a_0 
       x % m_1 = a_1
       ...
       x % m_n = a_n   (All m_i values must be co-prime.)

    Note that any number x_k = x + k*(a_0*a_1*...*a_n) can also be the solution.
    """
    prod = 1
    for m_i in m:
        prod *= m_i
    return sum((p := prod // m_i) * pow(p, -1, m_i) * a_i 
               for a_i, m_i in zip(a, m)) % prod

# N prime_list
# I {"version": "1.0", "typing": ["List"], "import": ["math"]}
def prime_list(limit: int) -> List[int]:
    """Returns a list of prime numbers up to the given integer."""
    if limit < 3: 
        return [2] if limit == 2 else []
    size = (limit - 3) // 2
    is_prime = [True] * (size + 1)
    for i in range(math.isqrt(limit - 3) // 2 + 1):
        if is_prime[i]:
            p = i + i + 3
            s = p * (i + 1) + i
            is_prime[s::p] = [False] * ((size - s) // p + 1)
    return [2] + [i + i + 3 for i, v in enumerate(is_prime) if v]

# N prime_list
# I {"version": "1.22", "import": ["math"]}
def prime_list(a: int, b: int = -1) -> list[int]:
    """Returns a list of prime numbers in the given range, [1, a] or [a, b]."""
    start, limit = (1, a) if b == -1 else (min(a, b), max(a, b))
    if limit < 3:
        return [2] if limit == 2 else []
    size = (limit - 3) // 2
    is_prime = [True] * (size + 1)
    for i in range(math.isqrt(limit - 3) // 2 + 1):
        if is_prime[i]:
            p = i + i + 3
            s = p * (i + 1) + i
            is_prime[s::p] = [False] * ((size - s) // p + 1)
    start_pos = 0 if start == 1 else (start - 2) // 2
    s = start_pos * 2 + 3
    ans = [] if start > 2 else [2]
    return ans + [i + i + s for i, v in enumerate(is_prime[start_pos:]) if v]