Number Theory Basics

What this covers

A handful of number-theory routines appear repeatedly in contest problems. None is long, but each has a cost that decides whether it fits the constraints. Knowing the cost is as important as knowing the code.

Divisors

To find every divisor of n, loop only to the square root. Divisors pair up: if d divides n, so does n / d, and one of the pair is always at most √n.

static List<Long> divisors(long n) {
    List<Long> result = new ArrayList<>();
    for (long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            result.add(d);
            if (d != n / d) {          // avoid adding the square root twice
                result.add(n / d);
            }
        }
    }
    return result;
}

This is O(√n). For n up to 10¹² that is a million iterations — fine.

The condition d * d <= n rather than d <= Math.sqrt(n) avoids floating-point rounding at the boundary. The d != n / d guard prevents listing the square root twice for perfect squares.

Primality of a single number

Trial division to the square root, skipping even numbers after 2.

static boolean isPrime(long n) {
    if (n < 2) return false;
    if (n < 4) return true;            // 2 and 3
    if (n % 2 == 0) return false;
    for (long d = 3; d * d <= n; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

O(√n). Good for n up to about 10¹⁴ as a one-off. If you need primality for many large numbers, use a Miller–Rabin test instead; for the ranges typical of contest problems, this suffices.

The early returns matter: n < 2 excludes 0, 1, and negatives, and 1 is not prime. That is a classic source of a wrong answer on the smallest test case.

Sieve of Eratosthenes

When you need every prime up to N, testing each individually is O(N√N). The sieve does it in roughly O(N log log N), which is effectively linear.

static boolean[] sieve(int n) {
    boolean[] composite = new boolean[n + 1];
    composite[0] = composite[1] = true;

    for (int i = 2; (long) i * i <= n; i++) {
        if (!composite[i]) {
            for (int j = i * i; j <= n; j += i) {
                composite[j] = true;
            }
        }
    }
    return composite;                  // composite[k] == false means k is prime
}

Two details carry the efficiency. The outer loop stops at √n, because any composite has a factor at or below its square root. The inner loop starts at i * i rather than 2 * i, because smaller multiples of i were already crossed off by smaller primes.

Note the (long) i * i cast in the outer condition — for n near 2 × 10⁹, i * i would overflow int.

A sieve up to 10⁷ uses about 10 MB as a boolean[] and runs in well under a second. Up to 10⁸ it becomes tight on both.

Smallest prime factor

A variant that stores, for each number, its smallest prime factor. This makes factorizing any number in the range O(log n) with no division loop.

static int[] smallestPrimeFactor(int n) {
    int[] spf = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) {                        // i is prime
            for (int j = i; j <= n; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    return spf;
}

static List<Integer> factorize(int x, int[] spf) {
    List<Integer> factors = new ArrayList<>();
    while (x > 1) {
        int p = spf[x];
        while (x % p == 0) {
            factors.add(p);
            x /= p;
        }
    }
    return factors;
}

Use this when a problem asks you to factorize many numbers all below some bound. Building the table once beats factorizing each number separately.

Factorizing a single large number

Without a precomputed table, divide out each factor as you find it.

static List<Long> primeFactors(long n) {
    List<Long> factors = new ArrayList<>();
    for (long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factors.add(d);
            n /= d;
        }
    }
    if (n > 1) factors.add(n);         // whatever remains is prime
    return factors;
}

The final if (n > 1) is essential and easy to forget. After dividing out everything up to √n, any remainder greater than 1 is itself a prime larger than √n — for example factorizing 14 leaves 7 after removing 2.

This is O(√n) and returns factors with multiplicity, so 12 gives [2, 2, 3].

GCD and LCM

The Euclidean algorithm, which is O(log min(a, b)).

static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

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

In lcm, dividing before multiplying matters. Writing a * b / gcd(a, b) computes the product first, which can overflow even when the final result would fit.

Java also provides java.math.BigInteger.gcd, but the three-line version is faster and avoids allocation.

Costs at a glance

Related