Find All Divisors of 36 Without Testing Every Number

A zero remainder identifies each divisor of 36

A candidate belongs in the divisor list exactly when dividing 36 by that candidate leaves a zero remainder. For candidate i, the test is 36 % i == 0. Start at i = 1 and move upward. The candidates 1, 2, 3, 4, and 6 pass this test, while 5 does not, because 36 divided by 5 leaves a remainder.

for (int i = 1; i <= 36; i++) {
    if (36 % i == 0) {
        // i is a divisor of 36
    }
}

Every divisor below the square root reveals one above it

A successful candidate gives you two divisors at once. If i divides 36 evenly, then 36 / i is its partner. Candidate 1 gives 36, candidate 2 gives 18, candidate 3 gives 12, and candidate 4 gives 9. Candidate 5 fails the zero-remainder test, so it has no whole-number partner.

The pairs move toward each other as i grows: 1 and 36, 2 and 18, 3 and 12, 4 and 9, then 6 and 6. Once the smaller member of a pair passes the square root of 36, which is 6, its partner would be smaller than the candidate and would already have been found. Testing candidates 7 through 36 cannot discover a new divisor.

for (int i = 1; i <= 6; i++) {
    if (36 % i == 0) {
        int partner = 36 / i;
        // i and partner are a divisor pair
    }
}

The square-root pair must be added only once

At i = 6, the partner is 36 / 6, which is also 6. This is different from the other pairs: 1 and 36 are two values, as are 2 and 18, 3 and 12, and 4 and 9. Because 36 is a perfect square, its square-root divisor meets itself.

if (36 % i == 0) {
    small.push_back(i);
    int partner = 36 / i;
    if (partner != i) {
        large.push_back(partner);
    }
}

The condition partner != i skips only the repeated 6. It does not skip any other divisor, because every other successful candidate below 6 has a different partner above 6. The final values still include one 6, exactly as the divisor list should.

if (36 % i == 0) {
    int partner = 36 / i;
    if (__________) {
        large.push_back(partner);
    }
}

Pair discovery order is not ascending divisor order

Finding both members immediately gives the pairs in discovery order, not in ascending order. For 36, the output would begin 1, 36, 2, 18, 3, 12, 4, 9, 6. The values are all correct, but the larger partner arrives before the next smaller candidate.

Keep the candidate in a small-divisor list and put each different partner in a large-divisor list. The small list becomes 1, 2, 3, 4, 6. The large list becomes 36, 18, 12, 9. Reverse the large list before appending it, because its discovery order runs from largest to smallest.

small divisors: 1 2 3 4 6
large divisors: 36 18 12 9
reversed large divisors: 9 12 18 36
final order: 1 2 3 4 6 9 12 18 36

Appending the small-divisor list to the reversed large-divisor list produces 1, 2, 3, 4, 6, 9, 12, 18, 36. The single 6 stays at the boundary because it is the only value whose pair is itself.