Number Theory

Number Theory in C

Number theory is the branch of mathematics dealing with integers and their properties. C's integer types make it an excellent language for implementing classic number-theoretic algorithms.

Greatest Common Divisor (GCD)

The GCD of two integers is the largest integer that divides both. The Euclidean algorithm computes it efficiently:

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

It works by repeatedly replacing (a, b) with (b, a % b) until b is zero. Then a is the GCD.

gcd(48, 18)   // 6
gcd(100, 75)  // 25

Least Common Multiple (LCM)

From the GCD, the LCM follows immediately:

$\text{lcm}(a, b) = \frac{|a \cdot b|}{\gcd(a, b)}$

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // divide first to avoid overflow
}

Primality Testing

A number is prime if it has no divisors other than 1 and itself. The basic trial-division test checks up to √n:

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

Only checking up to √n is sufficient — if n has a factor greater than √n, it must also have one smaller than √n.

is_prime(2)   // 1 (prime)
is_prime(17)  // 1 (prime)
is_prime(20)  // 0 (composite: 4×5)

Your Task

Implement gcd (using the Euclidean algorithm) and is_prime (trial division up to √n), then print:

1. gcd(48, 18)
2. gcd(100, 75)
3. is_prime(17)
4. is_prime(20)