Math & Number Theory

GCD via Euclid's algorithm

gcd(a, b) == gcd(b, a % b), down to gcd(x, 0) == x. LCM follows from a * b / gcd(a, b).

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

def lcm(a, b):
    return a * b // gcd(a, b)

Output:

gcd(48, 18)  # 6
lcm(4, 6)    # 12

Primality test

Trial division only needs to check divisors up to sqrt(n) — any factor larger than the square root has a matching factor smaller than it.

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

Output:

is_prime(97)   # True
is_prime(100)  # False

Sieve of Eratosthenes

To find all primes up to n, mark multiples of each prime as composite starting from p*p. This runs in O(n log log n) — far faster than testing each number individually.

def sieve(n):
    is_composite = [False] * (n + 1)
    primes = []
    for p in range(2, n + 1):
        if not is_composite[p]:
            primes.append(p)
            for multiple in range(p * p, n + 1, p):
                is_composite[multiple] = True
    return primes

Output:

sieve(30)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Modular arithmetic

For large results, take % (10**9 + 7) after every multiplication/addition to avoid overflow. Remember: (a * b) % m == ((a % m) * (b % m)) % m.