# Math & Number Theory — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/math-number-theory

> GCD, primality, and the Sieve of Eratosthenes — the recurring number-theory toolkit for interviews.

## 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)`.

```python
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.

```python
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.

```python
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`.