# Number Theory for Coding — GCD, Primes, Sieve and Fast Power

Source: https://skills101.in/learn/dsa/dsa-number-theory-basics — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

Many coding problems hide a little maths: "when do two buses arrive together again?", "how many primes are there below n?", "print the answer modulo 10⁹ + 7". You do not need advanced theory for these — a handful of short algorithms covers most placement and contest questions. This lesson explains each one, why it is fast, and the traps that cause wrong answers.

## 1. GCD and LCM with Euclid's algorithm

The **GCD** (greatest common divisor) of two numbers is the largest number that divides both. The **LCM** (least common multiple) is the smallest number that both divide.

**Euclid's algorithm** rests on one fact: `gcd(a, b) = gcd(b, a % b)`, and `gcd(a, 0) = a`. Any number that divides `a` and `b` also divides `a % b` (the remainder is `a` minus a multiple of `b`), so the common divisors do not change while the numbers shrink quickly.

```python
def gcd(a, b):
    steps = []
    while b:
        steps.append((a, b))
        a, b = b, a % b
    return a, steps

g, steps = gcd(252, 105)
print(steps, "->", g)

def lcm(a, b):
    return a // gcd(a, b)[0] * b      # divide first to keep numbers small

print(lcm(12, 18), lcm(4, 6), lcm(7, 5))
```

```text
[(252, 105), (105, 42), (42, 21)] -> 21
36 12 35
```

Two buses leave the college gate together, one every 12 minutes and one every 18 minutes. They leave together again after **lcm(12, 18) = 36** minutes. Euclid's algorithm takes **O(log(min(a, b)))** steps, because the numbers at least halve every two steps. Python has `math.gcd` and `math.lcm` built in; in Java you usually write the three-line loop yourself.

## 2. Is n prime?

A **prime** is a number greater than 1 whose only divisors are 1 and itself. To test `n`, you only need to try divisors up to **√n**: if `n = a × b` and both were larger than √n, the product would be larger than n. So one of them must be ≤ √n.

```python
def is_prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:              # same as d <= sqrt(n), without floats
        if n % d == 0:
            return False
        d += 1
    return True

print([x for x in range(1, 30) if is_prime(x)])
print(is_prime(97), is_prime(1_000_000_007), is_prime(91))
```

```text
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
True True False
```

This is **O(√n)** per number: about 31,600 steps for n = 10⁹ + 7. (91 = 7 × 13 is a classic trick question.)

## 3. The Sieve of Eratosthenes

To find **all** primes up to N, testing each number separately is wasteful. The **sieve** starts by assuming every number from 2 is prime, then for each prime `p` crosses out its multiples `p², p² + p, p² + 2p, …`.

![Sieve of Eratosthenes up to 60 in a grid of 10 columns: the 17 primes are green, and the other numbers are coloured by the first prime that crossed them out, 2, 3, 5 or 7](https://skills101.in/learn-img/dsa/sieve.svg)

Two details make it fast:

- Start crossing at `p × p`. Smaller multiples like `3p` were already crossed out by the smaller prime 3.
- Only primes `p ≤ √N` need to cross anything; after that, every number left is prime.

```python
def sieve(N):
    is_p = [True] * (N + 1)
    is_p[0] = is_p[1] = False
    p = 2
    while p * p <= N:
        if is_p[p]:
            for k in range(p * p, N + 1, p):
                is_p[k] = False
        p += 1
    return [i for i in range(N + 1) if is_p[i]]

print(sieve(60))
print(len(sieve(100)), len(sieve(1_000_000)))
```

```text
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
25 78498
```

The sieve runs in **O(N log log N)** time, which is nearly linear. It needs O(N) memory, so it suits N up to about 10⁷ in most judges.

## 4. Prime factors and divisors

Every number above 1 is a product of primes in exactly one way (for example 360 = 2³ × 3² × 5). To find the factors, divide out each `d` while it divides, up to √n. Whatever is left above 1 at the end is itself a prime.

Once you have `n = p₁^a × p₂^b × …`, the **number of divisors** is `(a + 1)(b + 1)…`, because each divisor picks a power from 0 to `a` for `p₁`, 0 to `b` for `p₂`, and so on.

```python
def factorise(n):
    f, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

for n in [360, 97, 1001]:
    f = factorise(n)
    count = 1
    for e in f.values():
        count *= e + 1
    print(n, f, "divisors:", count)
```

```text
360 {2: 3, 3: 2, 5: 1} divisors: 24
97 {97: 1} divisors: 2
1001 {7: 1, 11: 1, 13: 1} divisors: 8
```

## 5. Modular arithmetic and 10⁹ + 7

Answers such as "number of paths" grow enormous, so problems ask for the answer **modulo** `M`, usually `M = 10⁹ + 7`. It is a prime, and it is small enough that the product of two values below it fits in a 64-bit integer.

| Operation | Safe form |
|---|---|
| Addition | `(a + b) % M` |
| Multiplication | `(a * b) % M` — use `long` in Java |
| Subtraction | `((a − b) % M + M) % M` — avoid negatives |
| Division | multiply by the **modular inverse**, not `/` |

Take `% M` after **every** step, not only at the end; otherwise Java's `long` overflows silently. Division is different: `(a / b) % M` is wrong. Because `M` is prime, the inverse of `b` is `b^(M − 2) % M` (Fermat's little theorem), which needs fast power.

## 6. Fast power (binary exponentiation)

Computing `a^e` by multiplying `e` times takes O(e) — hopeless for `e = 10⁹`. **Fast power** uses the binary form of `e`: square the base at each step, and multiply it into the result whenever the current bit of `e` is 1.

![Fast power table for 3 to the power 13 mod 1000: 13 is 1101 in binary; four loop steps multiply the result by the base when the bit is 1 and square the base every time, giving 323](https://skills101.in/learn-img/dsa/fast-power.svg)

Since 13 = 8 + 4 + 1, `3¹³ = 3⁸ × 3⁴ × 3¹`. The loop runs once per bit: **O(log e)**.

```java
public class Main {
    static final long MOD = 1_000_000_007L;

    static long power(long base, long e, long mod) {
        long result = 1;
        base %= mod;
        while (e > 0) {
            if ((e & 1) == 1) result = result * base % mod;   // bit is 1
            base = base * base % mod;                         // square
            e >>= 1;
        }
        return result;
    }

    static long gcd(long a, long b) {
        while (b != 0) { long t = a % b; a = b; b = t; }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(power(3, 13, 1000));
        System.out.println(power(2, 10, MOD));
        System.out.println(power(2, 1_000_000_000L, MOD));
        long inv3 = power(3, MOD - 2, MOD);                   // modular inverse of 3
        System.out.println(inv3 + " " + (3 * inv3 % MOD));
        System.out.println(gcd(252, 105));
    }
}
```

```text
323
1024
140625001
333333336 1
21
```

`3 × 333333336 % M = 1`, so 333333336 acts as "1/3" in modulo arithmetic: to divide by 3, multiply by it. Python's built-in `pow(a, e, m)` does the same fast power for you.

## Common mistakes

- Testing primes up to `n − 1` instead of √n, which is far too slow for large n.
- Treating 1 as a prime. It is not; the smallest prime is 2.
- Computing `a * b / gcd(a, b)` in Java with `int`, which can overflow before the division. Divide first: `a / gcd * b`, using `long`.
- Taking `% M` only at the end, after the value has already overflowed.
- Writing `(a − b) % M` in Java or C++ and getting a negative answer.
- Dividing under a modulus with `/` instead of multiplying by the modular inverse.

## Quick recap

- `gcd(a, b) = gcd(b, a % b)`; `lcm = a / gcd × b`; O(log) steps.
- Prime test: try divisors up to √n.
- Sieve: cross out multiples of each prime from p², only for p ≤ √N; O(N log log N).
- Divisor count from the prime factorisation: multiply (exponent + 1).
- Under 10⁹ + 7: mod after every step, fix negatives, divide with the inverse `b^(M − 2)`.
- Fast power: square the base, multiply on 1-bits; O(log e).


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-number-theory-basics