Divisors, primes and GCD

Which numbers divide 36 exactly? The first idea is to try every number from 1 to 36. That works, but for a number near a billion it means a billion checks.

This lesson shows why you can stop at the square root, then reuses that one loop for primes and perfect numbers. It ends with Euclid's method for the GCD, a 2,300-year-old loop that is still the fastest way.

Read the problem

Ask these before you code:

• n = 1? It has one divisor: 1.
• A perfect square? 36 = 6 × 6. List 6 once, not twice.
• Order? The output must be sorted.
• What is n? Here n is a value, not a length. A loop from 1 to n costs n steps, even though the input is one number.

The sheet keeps n at 1,000 or less, so any loop passes. Interviewers ask the next question: what if n is 10⁹?

Brute force: try every number

Check each i from 1 to n. Keep it when n % i is 0.

┌───────────────────────────────────────────────────────┐
│                                                       │
│        i  1  2  3  4  5  6  7  8  9 10 11 12 ... 36   │
│   36 % i  0  0  0  0  1  0  1  4  0  6  3  0 ...  0   │
│    keep?  ▓  ▓  ▓  ▓  ·  ▓  ·  ·  ▓  ·  ·  ▓ ...  ▓   │
│                                                       │
└───────────────────────────────────────────────────────┘

JavaPythonTypeScript

List<Integer> divisors(int n) {
    List<Integer> result = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) result.add(i);
    }
    return result;
}

The loop runs n times, one remainder each. So it is O(n). For n = 10⁹ that is a billion checks: about 10 seconds against a budget of 1.

The key insight: divisors come in pairs

Every divisor i has a partner, n / i. Write the pairs for 36:

┌────────────────────────────────────────────┐
│                                            │
│      small × big                           │
│        1   ×  36   ─┐                      │
│        2   ×  18    │ small side           │
│        3   ×  12    │ below 6              │
│        4   ×   9   ─┘                      │
│        6   ×   6   ← the sides meet        │
│        9   ×   4   ─┐                      │
│       12   ×   3    │ the same pairs,      │
│       18   ×   2    │ flipped              │
│       36   ×   1   ─┘                      │
│                                            │
└────────────────────────────────────────────┘

In every pair, the small side is at most √n. So find the small side of each pair, and you get the big side for free.

The loop condition i * i <= n means "i is at most √n". It avoids a square root call and its decimals.

Optimal: stop at the square root

1. For i = 1, 2, 3, … while i * i <= n:
2. If i divides n, keep i in small and n / i in big.
3. When i and n / i are equal (a perfect square), keep it once.
4. small comes out increasing and big comes out decreasing. Join small with big reversed.

Here it is on 36. The cells are the values of i the loop tries.

JavaPythonTypeScript

List<Integer> divisors(int n) {
    List<Integer> small = new ArrayList<>();
    List<Integer> big = new ArrayList<>();
    for (int i = 1; i * i <= n; i++) {
        if (n % i != 0) continue;
        small.add(i);
        if (i != n / i) big.add(n / i); // the partner, unless i is the square root
    }
    Collections.reverse(big);
    small.addAll(big);
    return small;
}

• Time: the loop runs about √n times, so O(√n). No sort is needed.
• Space: the output only. A number has few divisors: 1,000 has 16.
• n = 1: i = 1 passes the check, its partner is 1 again, so the answer is [1].
• In Python, the partner is n // i. Plain / would give a float such as 36.0.
• In Java, i * i overflows an int once i passes 46,340. Up to n = 10⁹ that never happens. For n near 2³¹, write (long) i * i <= n.

Side by side

Same loop: primes and perfect numbers

A prime has no divisor between 2 and √n. If one exists, its pair proves n is not prime.

JavaPythonTypeScript

boolean isPrime(int n) {
    if (n < 2) return false; // 0 and 1 are not prime
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false; // found a pair, so not prime
    }
    return true;
}

The rest of the list reuses the same pairs loop:

A perfect number equals the sum of its divisors below itself: 6 = 1 + 2 + 3, and 28 is the next one.

Count of primes passes on the sheet, where N ≤ 1,000. On LeetCode's "Count Primes", N reaches 5 × 10⁶, and N√N is about 10¹⁰ steps. That version needs the sieve, in the Advanced part.

GCD with Euclid's method

The GCD of two numbers is the largest number that divides both.

Brute force

Try every number from min(a, b) down to 1. The first one that divides both is the answer. When the GCD is 1, as for 11 and 13, the loop runs all the way down: O(min(a, b)).

Euclid's idea

Any number that divides both a and b also divides a % b. So gcd(a, b) equals gcd(b, a % b), and the second pair is smaller.

Repeat until the second number is 0. The first number is the GCD.

┌────────────────────────────────────────────┐
│                                            │
│        a     b     a % b                   │
│       48    18      12                     │
│       18    12       6                     │
│       12     6       0                     │
│        6     0    stop: the GCD is 6       │
│                                            │
└────────────────────────────────────────────┘

JavaPythonTypeScript

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b; // the remainder
        a = b; // b moves left
        b = r; // the remainder takes its place
    }
    return a;
}

• Python and TypeScript move both values in one line. Java has no such swap, so it holds the remainder in r for a moment.
• If a is smaller than b, the first pass swaps them: gcd(18, 48) becomes gcd(48, 18).
• The remainder at least halves every two passes, so the cost is O(log min(a, b)). For any two numbers up to 1,000, it takes at most 15 passes.
• A real use: a 1920 × 1080 screen has a GCD of 120, so its ratio is 16:9.

LCM for free

The LCM comes from the GCD: lcm(a, b) = a / gcd(a, b) * b. Divide first, so the product stays small. For 4 and 6: 4 / 2 × 6 = 12.

• In Python, write a // gcd(a, b) * b. Python also ships math.gcd and math.lcm.
• In Java, the LCM of two ints can pass the int limit. Return a long when the inputs are large.

How to spot this pattern

The template for anything about divisors:

JavaPythonTypeScript

for (int i = 1; i * i <= n; i++) {
    if (n % i != 0) continue;
    // use i, and its partner n / i when it is different
}

take U forwardYouTube

Read more

• Euclidean algorithm on Wikipedia, with the proof and pictures
• Prime number on Wikipedia, including trial division
• Perfect number on Wikipedia: 6, 28, 496 and 8,128
• Divisors of a Number on takeUforward, to solve it yourself

Next: your first array problems, where one pass over the array answers the question.