Divisors of a number

A divisor of a number n is a number from 1 to n that divides n with no remainder, such as 4 for 12. All divisors of a number up to about 10^{12} can be listed with about 10^6 tries, by going only up to its square root. The number and the sum of the divisors also follow from the prime factorization without listing them, and a different loop finds the divisors of every number up to about 10^6 at once. To split a number into primes instead, see prime factorization.

Explanation

The plain way to find the divisors of 12 is to try every number from 1 to 12 and keep those that divide it. Twelve tries find six divisors: 1, 2, 3, 4, 6 and 12.

Fig. 1. Trying every number from 1 to 12. The green ones divide 12.

Problems ask for the divisors of numbers up to 10^{12}, and trying them all takes 10^{12} tries. By the rule of thumb from time complexity, about 10^8 simple steps per second, that takes hours.

12 is too small to show where the work can be saved, so take a bigger number with more divisors, 36. Its divisors are 1, 2, 3, 4, 6, 9, 12, 18 and 36, and trying every number finds them in 36 tries.

The usual first idea is to stop halfway. Apart from 36 itself, no divisor of 36 is bigger than 18: the smallest divisor after 1 is at least 2, and 36 / 2 = 18. So try 1 to 18 and add 36 at the end. That is 18 tries instead of 36, and the answer is still right. But for 10^{12} it is still 5 \cdot 10^{11} tries, which takes hours.

Stopping at 18 works because 2 · 18 = 36: the divisor 18 comes together with the divisor 2. Every divisor comes with such a partner, 36 divided by it. The pairs for 36 are 1 and 36, 2 and 18, 3 and 12, 4 and 9, and 6 with itself. In each pair one number is at most 6 and the other is at least 6, because if both were bigger than 6, their product would be bigger than 6 · 6 = 36.

Fig. 2. Every pair has one number at most 6, the square root of 36. Trying 1 to 6 finds the green numbers, and their partners are the blue ones.

This is the pair loop: try only the numbers whose square is at most n, here 1 to 6, and each time one divides n, write down both it and its partner. That is 6 tries for 36 instead of 18, and 10^6 for 10^{12}.

At 6 the partner is 36 / 6 = 6 again, so write it once, or 36 seems to have 10 divisors.

The partners come out from largest to smallest, 36, 18, 12, 9, so printing each pair as it is found gives 1 36 2 18 3 12 4 9 6. Keep the numbers tried in a small list and the partners in a big list, and read the big list backwards after the small one. The player below runs the pair loop on 36.

The pair loop lists the divisors of 36. The top row holds the numbers 1 to 6 to try, below it are the small list and the big list, both empty, and the bottom row is the output.

Try the next number, 1: 36 % 1 = 0, so take the pair. The small list gets 1 and the big list gets its partner 36 / 1 = 36. The outlined cells are the ones that change in each step.

Try 2: 36 % 2 = 0, so the small list gets 2 and the big list gets 36 / 2 = 18.

Try 3: 36 % 3 = 0, so the small list gets 3 and the big list gets 36 / 3 = 12.

Try 4: 36 % 4 = 0, so the small list gets 4 and the big list gets 36 / 4 = 9.

Try 5: 36 % 5 = 1, so 5 doesn't divide 36 and nothing is written.

Try 6: 6 · 6 = 36 and 36 % 6 = 0, so 6 is its own partner: write it once, in the small list only.

The next number would be 7, but 7 · 7 = 49 > 36, so the loop stops after 6 tries.

Join the lists: the output is the small list 1 2 3 4 6, then the big list read from the end, 9 12 18 36.

1/9

Fig. 3. Step through with the buttons or the arrow keys. Green numbers divide 36.

A number up to 10^{12} has at most 6720 divisors (963 761 198 400 has that many), so the lists stay short.

Count and sum from the prime factors

For one number up to about 10^{12}, the pair loop gives the count and the sum of the divisors directly: count the list or add it up. Formulas from the prime factorization are needed for numbers the loop can't handle, such as a number given by its primes, or a number up to 10^{18} whose primes are all small.

First factor: 36 = 2^2 \cdot 3^2, so each divisor of 36 is a power of 2 (1, 2 or 4) times a power of 3 (1, 3 or 9). A divisor can use only the primes of 36, each at most as many times as 36 does, so the divisors fill a table with one row per power of 2 (2 + 1 rows) and one column per power of 3 (2 + 1 columns), each in exactly one cell. Then multiply: 36 has 3 · 3 = 9 divisors. In general, the count is each exponent plus 1, all multiplied together.

Fig. 4. Every divisor of 36 is a power of 2 times a power of 3, once each. The grey numbers are the row sums.

The first row adds up to 1 · (1 + 3 + 9), the second to 2 · (1 + 3 + 9), the third to 4 · (1 + 3 + 9). All together that is (1 + 2 + 4) · (1 + 3 + 9) = 7 · 13 = 91. In general, multiply together 1 + p + p^2 + \dots + p^a for each prime $p$ with exponent $a$.

Divisors of every number up to N

Some problems need the divisors of every number up to 10^6. The pair loop for each number takes about 6.7 \cdot 10^8 tries in total, the sum of the square roots of all these numbers: about 7 seconds by the rule of thumb.

Keep a counter for every m up to N, all starting at 0. Each d from 1 to N walks through its multiples d, 2d, 3d, … and adds 1 to each one's counter. The counter of m goes up once for each divisor of m, so it ends at the number of divisors of m. Adding d instead of 1 gives the sum of divisors.

Fig. 5. Each d adds 1 to the counters of d, 2d, 3d, …; the bottom row ends as the divisor counts.

Up to 12, the number 1 has 12 multiples, 2 has 6, 3 has 4, and so on: 35 steps. In general the loop takes N / 1 + N / 2 + … + N / N steps. This sum is about $N\ln N$ (ln is the natural logarithm, about 14 for 10^6), so the loop takes O(N \log N) time, about 1.4 \cdot 10^7 steps for N = 10^6.

Every step lands on a divisor, so the number of steps is the total of the bottom row. The pair loop wastes most of its tries instead: a number up to 10^6 has about 14 divisors on average, but the pair loop tries up to 1000 numbers for it.

Implementation

In the code the number is n, the number tried is d and its partner is n / d. Both n and d are long long, because n goes up to 10^{12}. The small list is a vector small, and the big list is big.

1. Try the next number: d = 1, 2, 3, … while d * d <= n.

2. Take the pair: if n % d == 0, put d in small and, if d != n / d, put n / d in big.

3. Join the lists: print small as it is, then big from the end.

The program reads one number n from 1 to 10^{12} and prints its divisors in increasing order. The call reverse(big.begin(), big.end()) turns the big list around. For the main example the input is:

36

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<long long> small, big;
    for (long long d = 1; d * d <= n; d++) {   // try the next number
        if (n % d == 0) {                       // take the pair
            small.push_back(d);
            if (d != n / d) big.push_back(n / d);
        }
    }
    reverse(big.begin(), big.end());            // join the lists
    for (long long x : small) cout << x << ' ';
    for (long long x : big) cout << x << ' ';
    cout << '\n';
}

The condition d * d <= n stays in integers, and the loop takes O(\sqrt{n}) time.

Count and sum from the prime factors

The program first factors n by trial division: it divides out each prime p and counts its exponent a. Then it multiplies cnt by a + 1 and sum by 1 + p + ... + p^a. A leftover bigger than 1 is a prime with exponent 1. Like the pair loop, it takes at most about \sqrt{n} steps, the worst case being a large prime left over. If all primes of n are known to be at most 1000, stop p at 1000 instead: a number up to 10^{18} then takes 1000 steps, and its divisor sum still fits in long long. For the input 36 it prints 9 91.

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long cnt = 1, sum = 1;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;
        int a = 0;                              // factor: divide p out, count how many times
        while (n % p == 0) {
            n /= p;
            a++;
        }
        long long term = 1, power = 1;          // multiply: 1 + p + ... + p^a
        for (int i = 0; i < a; i++) {
            power *= p;
            term += power;
        }
        cnt *= a + 1;
        sum *= term;
    }
    if (n > 1) {                                // the leftover is a prime with exponent 1
        cnt *= 2;
        sum *= 1 + n;
    }
    cout << cnt << ' ' << sum << '\n';
}

Every number up to N

The program reads N and fills cnt[m], the number of divisors of m, for every m up to N. For the input 12 it prints 1 2 2 3 2 4 2 4 3 4 2 6.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> cnt(N + 1, 0);
    for (int d = 1; d <= N; d++) {
        for (int m = d; m <= N; m += d) {       // walk the multiples
            cnt[m]++;                           // cnt[m] += d for the sum; divs[m].push_back(d) to list them
        }
    }
    for (int i = 1; i <= N; i++) cout << cnt[i] << ' ';
    cout << '\n';
}

It takes O(N \log N) time and $O(N)$ memory. Keeping the lists of divisors themselves, in a vector<vector<int>> divs, gives each list in increasing order but stores about 1.4 \cdot 10^7 numbers for N = 10^6, about 56 MB for the numbers alone, so keep them only when the problem needs them.

Problems on perfect and amicable numbers use proper divisors, all divisors except the number itself. Subtract n from the sum.

Similar algorithms

The primality test runs the same loop up to the square root but stops at the first divisor bigger than 1.

The sieve of Eratosthenes has the same shape as the multiples loop, but it walks the multiples of primes only and just marks them.

The common divisors of two numbers are the divisors of their greatest common divisor. Find it with the Euclidean algorithm and list its divisors.

Practice