Complexity

Number-theory complexity is often stated in terms of the value of the input, not the number of inputs. If an algorithm that takes a single number n runs in O(n), it is exponential in the input length, which is the digit count log n. Keep that distinction in mind. This chapter summarizes time and space costs and compares the alternatives.

Euclidean algorithm: O(log min(a, b))

Every two remainder steps at least halve the larger value, so the loop runs O(log min(a, b)) times; the extended version does a constant factor more work per step. The slowest inputs are consecutive Fibonacci numbers (Lamé's theorem): the quotient is 1 every time, so each step shrinks the numbers as little as possible.

def gcd_steps(a: int, b: int) -> int:
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return steps

fib = [1, 1]
while len(fib) < 50:
    fib.append(fib[-1] + fib[-2])

print(gcd_steps(fib[49], fib[48]))  # 48 — numbers around 1.3 × 10^10, only 48 steps
print(gcd_steps(10**18, 3))         # 2

No pair of 64-bit values needs more than about 100 steps, so in practice you can treat GCD as constant time.

Fast exponentiation: O(log e)

The loop runs once per bit of the exponent e, with at most two multiplications and reductions per iteration. Multiplying e times is O(e), which never finishes for e = 10^18; fast exponentiation needs about 60 iterations. Space is O(1). Applying the same idea to matrices computes linear recurrences such as Fibonacci numbers in O(k^3 log n).

Sieve of Eratosthenes: O(n log log n)

Each prime p crosses out about n / p slots, so the total work is n × (1/2 + 1/3 + 1/5 + …), and the sum of prime reciprocals grows like log log n. Even for n = 10^7, log log n is about 3, so the sieve is nearly linear. Space is O(n), down to n / 8 bytes with a bit array.

The linear sieve (Euler's sieve) crosses out each composite exactly once for O(n), and records the smallest prime factor (SPF) of every number as a bonus. With an SPF table, any number up to n factors in O(log n).

def linear_sieve(n: int) -> tuple[list[int], list[int]]:
    spf = [0] * (n + 1)          # spf[k] = smallest prime factor of k
    primes: list[int] = []
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p
    return primes, spf

def factorize(k: int, spf: list[int]) -> dict[int, int]:
    factors: dict[int, int] = {}
    while k > 1:
        p = spf[k]
        factors[p] = factors.get(p, 0) + 1
        k //= p
    return factors

primes, spf = linear_sieve(1000)
print(len(primes))          # 168
print(factorize(360, spf))  # {2: 3, 3: 2, 5: 1}