Prime factorisation and divisor counts

Why this matters when you build with AI

An AI tool will often write a loop that tests every candidate divisor from 1 up to n to count the divisors of n. For one small n this is fine. A contest problem can give you 200000 queries with n up to 1000000. The same loop then runs about 2 × 10^11 steps, and the judge stops the program with a time limit exceeded (TLE) verdict. The code is correct. It prints the right numbers on the sample. Nothing in a quick read shows the problem, so you find it only by counting the loop steps against the limits.

This lesson gives you three tools. The first is trial division, which factors one number in about the square root of its size. The second is a smallest prime factor table, which lets you factor many numbers quickly. The third is a set of formulas that turn a factorisation into the number of divisors, the sum of divisors and the product of divisors.

The examples are C++17. We compiled every program with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2 in a scratch folder, and we tested each one as described below. We do not give a Python version of this lesson's code. The table loops over millions of entries, and Python runs such loops far more slowly than C++.

The idea: a prime factorisation

A prime is a whole number greater than 1 whose only divisors are 1 and itself. Every whole number above 1 can be written as a product of primes, and the list of primes is the same whichever order you multiply them in. This is the fundamental theorem of arithmetic. Its consequence is that each number has exactly one prime factorisation.

Take 360. It is 2 × 2 × 2 × 3 × 3 × 5. We write it compactly as 2^3 × 3^2 × 5^1. The exponent of each prime says how many times that prime appears. We will call this the factorisation of n.

The factorisation tells you almost everything about the divisors of n. We come back to that in the section on counting divisors.

Trial division for one number

Trial division means trying each candidate prime p as a divisor of n. If p divides n, you divide it out as many times as it goes in, and you record p and how many times you divided. The loop stops when p times p is greater than n.

Why stop at the square root? Suppose n has a prime factor larger than its square root. Then n has at most one such factor, because two of them would multiply to more than n. So once you have removed every prime up to the square root, what is left over is either 1 or one prime. The leftover is the last factor, and it is not divided further.

Here is the process for 360, done by hand.

Start with p = 2. Divide 360 by 2 three times to get 45. Record 2 with exponent 3.
Move to p = 3. Divide 45 by 3 twice to get 5. Record 3 with exponent 2.
Move to p = 4. Now 4 times 4 is 16, which is greater than 5, so the loop stops.
The leftover 5 is greater than 1, so it is the last prime with exponent 1.

The result is 2^3 × 3^2 × 5^1. Candidates such as 4 and 6 are tried when they come up, but they never divide, because 2 and 3 have already been removed. The code below is the trial division version.

// Trial division: try every p with p * p <= n.
// Cost is about sqrt(n) steps, so this is fine for one n up to about 1e12.
vector<pair<ll, int>> factor_trial(ll n) {
    vector<pair<ll, int>> f;
    for (ll p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int e = 0;
            while (n % p == 0) {
                n /= p;
                e++;
            }
            f.push_back({p, e});
        }
    }
    if (n > 1) f.push_back({n, 1});  // whatever is left is one prime
    return f;
}

Three details in this code matter. The variable p is a 64-bit ll, because p * p for p near 10^6 is near 10^12, which does not fit in a 32-bit int. The final if (n > 1) line is required, because a prime such as 7 never enters the loop. Its result is {7, 1} only because of that line. Without it, factor_trial(7) returns an empty list.

For one n near 10^12, the loop runs about 10^6 times. That is fast. For 10^5 such numbers it runs about 10^11 times, which is too slow. Many numbers need a table.

Factor many numbers with a smallest prime factor table

If you have many queries with n up to a bound N, build a table once. The table spf stores for each x the smallest prime that divides x. Once you have that table, you can factor any x up to N by repeated lookup.

The table is built with a sieve, the method from the sieves lesson of this module. Go through x from 2 upwards. If spf[x] is still 0 when you reach x, no smaller prime has marked x, so x is prime. Then mark every multiple of x that is still unmarked with x. Because you go in increasing order, the first prime to reach a number is its smallest prime factor.

Here is a small example with N = 12. Start with an empty table. At x = 2, nothing has been marked, so 2 is prime. Mark 2, 4, 6, 8, 10 and 12 with the value 2. At x = 3, the entry is still 0, so 3 is prime. Mark 3, 9 with 3, since 6 and 12 are already marked. At x = 5 and x = 7 and x = 11, the entries are still 0, so these are primes, and each marks only itself within this range. The result is spf[12] = 2, spf[9] = 3 and spf[11] = 11.

To factor x, look up p = spf[x], divide x by p as many times as possible, and repeat with the result. Each step removes one prime factor, so the number of steps is the number of prime factors counted with multiplicity. For x up to 10^6 this is at most 19, because 2^19 is 524288 and 2^20 is above 10^6.

// spf[x] = smallest prime factor of x, for 2 <= x <= N.
// If spf[i] is still 0 when we reach i, nothing smaller divides i, so i is prime.
vector<int> build_spf(int N) {
    vector<int> spf(N + 1, 0);
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0) {
            for (ll j = i; j <= N; j += i)
                if (spf[j] == 0) spf[j] = i;
        }
    }
    return spf;
}
 
// Factor n with the table. Each loop step removes one prime, so a number
// with k prime factors (with multiplicity) takes about k steps.
vector<pair<int, int>> factor_spf(int n, const vector<int>& spf) {
    vector<pair<int, int>> f;
    while (n > 1) {
        int p = spf[n], e = 0;
        while (n % p == 0) {
            n /= p;
            e++;
        }
        f.push_back({p, e});
    }
    return f;
}

The table for N = 10^6 holds 10^6 + 1 integers, about 4 MB. The build is the simple sieve described above, which takes roughly N log log N steps. The linear sieve from the sieves lesson builds the same table in time proportional to N. You can swap it in without changing factor_spf.

A table is only as large as the biggest number you will ever factor. Build it once, after you read all queries, and size it to the largest n in the input. Reading spf[n] for n above the table size is undefined behaviour. In practice it reads memory outside the table and gives a wrong answer or a crash, not a clear error.

Counting and summing divisors

The factorisation gives the divisors directly. Let n = p1^e1 × p2^e2 × ... × pk^ek. Every divisor of n has the form p1^f1 × ... × pk^fk, where each fi is a whole number from 0 to ei. Choosing the exponents is independent, one prime at a time. So the total number of divisors is the number of choices, which is a product.

Number of divisors

The number of divisors d(n) is the product of (ei + 1) over all primes.

For 360 = 2^3 × 3^2 × 5^1, the exponents are 3, 2 and 1, so d(360) = 4 × 3 × 2 = 24. You can check this by listing: for each prime, choose how many copies to keep from 0 to its exponent, which gives 4 choices for the 2s, 3 for the 3s and 2 for the 5s.

The +1 matters. A prime with exponent 0 is not in the number at all, so it contributes one choice, not zero. Forgetting the +1 makes the answer zero for every number that has a prime with exponent 1, which is almost every number.

Sum of divisors

The sum of divisors sigma(n) is the sum of all divisors. It factors across the primes in the same way. For each prime power, the sum is 1 + p + p^2 + ... + p^e, and sigma(n) is the product of these sums.

For 360 this gives (1 + 2 + 4 + 8) × (1 + 3 + 9) × (1 + 5) = 15 × 13 × 6 = 1170. The code adds the powers in a loop, which avoids a division. A closed form (p^(e+1) - 1) / (p - 1) also works for exact integers, but it needs an exact division. Under a modulus it needs a modular inverse, which lesson 5 covers.

// Number of divisors: product of (e + 1) over the prime powers p^e.
ll divisor_count(const vector<pair<int, int>>& f) {
    ll d = 1;
    for (auto [p, e] : f) d *= (e + 1);
    return d;
}
 
// Sum of divisors: product of (1 + p + p^2 + ... + p^e).
ll divisor_sum(const vector<pair<int, int>>& f) {
    ll s = 1;
    for (auto [p, e] : f) {
        ll term = 0, pw = 1;
        for (int k = 0; k <= e; k++) {
            term += pw;
            pw *= p;
        }
        s *= term;
    }
    return s;
}

Both functions read the factorisation, not n itself, so they cost time in the number of distinct primes, plus the exponents for the sum.

Product of divisors

The product of all divisors of n is n^(d(n)/2). The reason is pairing. The divisors can be paired as (d, n/d), and each pair multiplies to n. If d(n) is even, there are d(n)/2 pairs, which gives the formula.

Take n = 12. Its divisors are 1, 2, 3, 4, 6 and 12, so d = 6. Their product is 1 × 2 × 3 × 4 × 6 × 12 = 1728, and 12^3 = 1728. The formula holds.

When d(n) is odd, the formula needs care. An odd count means one divisor is paired with itself, which happens only when d = n/d, so d is the square root of n. Then n is a perfect square, and the product is (sqrt n)^d. Take n = 36. It has nine divisors, and the product is 6^9 = 10077696. A program that writes pow(36, 9 / 2) gets 36^4 = 1679616 instead, because 9 / 2 is 4 in integer division. We ran that exact mistake and got both numbers.

Worked example: divisor count and sum for many queries

The problem. You get Q queries, where Q is at most 200000. Each query is one number n, with 1 at most n at most 10^6. For each n, print the number of divisors and the sum of the divisors, separated by a space.

The approach. Build the table once for the largest possible n. For each query, factor with the table, then apply the two formulas. The table costs about N log log N steps once, and each query costs a few lookups.

The program. It is the trial and table functions above, plus this main. Compile it as one file.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// (the functions factor_trial, build_spf, factor_spf, divisor_count and divisor_sum from above go here)
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int N = 1000000;
    vector<int> spf = build_spf(N);
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        auto f = factor_spf(n, spf);
        cout << divisor_count(f) << ' ' << divisor_sum(f) << '\n';
    }
}

We compiled this with the functions in place and ran it on this input:

The real output of our run was:

Read each line against the formulas. For n = 1, the factorisation is empty, so the divisor count is the empty product 1 and the sum is 1. For n = 12 = 2^2 × 3, the count is 3 × 2 = 6 and the sum is 7 × 4 = 28. For n = 36 = 2^2 × 3^2, the count is 3 × 3 = 9 and the sum is 7 × 13 = 91. For the prime 97, the count is 2 and the sum is 1 + 97 = 98.

How we checked it. We wrote a test program in C++, compiled with the same flags. It did three things. First, it checked that factor_trial and factor_spf return the same factorisation for every n from 1 to 200000. Second, it checked the divisor count and divisor sum against a brute force loop that tests every d from 1 to n, for every n from 1 to 3000. Third, it checked the product formula n^(d/2) for every n up to 100, using 128-bit integers to compare the squares of both sides. The program printed PASS.

For speed, we generated 200000 random queries with n up to 10^6 and ran the program on them. On the machine we used, a WSL2 Linux system, the whole run took 0.098 seconds of wall time, including building the table. Your numbers will differ with your machine and compiler, but the shape holds: the table dominates when queries are few, and the queries dominate when they are many.

Exercise: the number with the most divisors in a range

The problem. You get two numbers L and R, with 1 at most L at most R at most 10^6. Print the smallest x in the range [L, R] that has the largest number of divisors, followed by that number of divisors.

What to try first. Build the table up to R. Loop over every x from L to R, factor it with the table, compute the divisor count, and keep the best. Use a strict comparison when you update the best, so that a tie keeps the earlier, smaller number.

Here are two sample inputs and their real outputs.

1 100

60 12

1 1000000

720720 240

The number 60 = 2^2 × 3 × 5 has 3 × 2 × 2 = 12 divisors, and no smaller number up to 100 has as many. The number 720720 has 240 divisors. The same program with a different tie-break rule would print a different number when two numbers tie, so the strict comparison is part of the answer.

Here is the main for this exercise. It uses the same functions as above, so compile it with the same function block.

int main() {
    ll L, R;
    cin >> L >> R;
    vector<int> spf = build_spf((int)R);
    ll best = L, bestD = 0;
    for (ll x = L; x <= R; x++) {
        ll d = divisor_count(factor_spf((int)x, spf));
        if (d > bestD) {  // strict ">" keeps the smallest number on a tie
            bestD = d;
            best = x;
        }
    }
    cout << best << ' ' << bestD << '\n';
}

We checked this against a brute force program in Python. The brute force counts divisors by testing every d up to x, and takes the smallest x with the most. We ran 300 random ranges with R up to 2000, and the outputs matched in all 300 cases.

Complexity

factor_trial(n) takes about sqrt(n) steps. For n near 10^12 that is about 10^6 steps.
build_spf(N) takes about N log log N steps with the simple sieve, and memory about 4 bytes per entry.
factor_spf(n) takes one step per prime factor counted with multiplicity. For n up to 10^6 that is at most 19.
divisor_count takes time in the number of distinct primes. divisor_sum also loops over the exponents.

Common mistakes

Trial division up to n instead of the square root. The symptom is a TLE on large inputs, such as one n near 10^12, where the loop runs 10^12 times. The fix is the condition p * p <= n.
Losing the last prime. Without the if (n > 1) line, factor_trial(7) returns an empty list. The symptom is a divisor count of 1 for a prime. Test with n = 1, n = 2, n = 7 and n = 12 every time you write a factoriser.
Overflow in p * p. If p is an int, then p * p for p near 10^6 is about 10^12, which overflows a 32-bit integer. The symptom is a loop that stops early or runs far too long. Use long long for p and n.
Integer division in the product formula. For odd d(n), pow(n, d / 2) is wrong. We ran this for n = 36. The correct product is 10077696, and 36^4 is 1679616. Use the square root when d(n) is odd.
Table smaller than the input. Reading spf[n] above the table size is undefined behaviour. Build the table to the largest n in the input.
Forgetting the +1 in the divisor count. The symptom is an answer of 0 for numbers with a prime exponent of 1, such as 6, which should have 4 divisors.
Special-casing n = 1. The empty factorisation already gives the right answers, 1 divisor and sum 1. Adding a special case is harmless but usually signals that the author did not trust the formulas.

A prompt to check AI output

Give the prompt below to an AI tool with your code. A good answer names the loop that runs the most, states its count as a function of the limits, and gives a concrete input that makes it too slow or wrong.

Here is my C++ code that counts the divisors of each query number. The limits are
Q up to 200000 and n up to 1000000. Do not rewrite it yet. Tell me how many loop
steps the worst case takes, as a formula in Q and n. Then name one input that
would give a wrong answer or a time limit error, and say how you know.

When you read the reply, check two things. The loop count must be written as a formula, not as a vague phrase such as "fast enough". The counterexample must be a real input, which you can run. AI tools often propose trial division up to n, or they forget the leftover prime. Both show up in the tests from the mistakes list.

Checklist

Trial division runs while p * p <= n, with p and n as 64-bit integers.
The leftover factor above 1 is added to the result.
The smallest prime factor table covers the largest n you will factor.
The divisor count is the product of e + 1.
For odd d(n), use the square root in the product formula, not integer division.
Test with n = 1, a prime, the square of a prime, and a power of 2.

Practice

Each practice problem has a hint and an answer under the line "Show the answer". Try each one before you read the answer.

Find d(720) and the sum of divisors of 720 using only the factorisation. Hint: write 720 as a product of prime powers first.

Show the answer 720 = 2^4 × 3^2 × 5. The divisor count is 5 × 3 × 2 = 30. The sum is (1 + 2 + 4 + 8 + 16) × (1 + 3 + 9) × (1 + 5) = 31 × 13 × 6 = 2418. We checked both numbers with Python by testing every divisor of 720.

Factor 1234567890 by trial division. Hint: divide out 2 and 5 first, then 3 twice, then test the remaining number up to its square root.

Show the answer 1234567890 = 2 × 3^2 × 5 × 3607 × 3803. The divisor count is 2 × 3 × 2 × 2 × 2 = 48. Once 3607 is divided out, 3803 is left. The next candidate, 3608, has a square above 3803, so the loop stops and 3803 is the last prime. We factored this number with a short Python trial division and got the same five primes.

Compute the product of all divisors of 100 with the formula, and check it by multiplying the divisors. Hint: 100 has an odd divisor count, so use the square root.

Show the answer The divisor count of 100 = 2^2 × 5^2 is 3 × 3 = 9, which is odd, so 100 is a perfect square. The product is (sqrt 100)^9 = 10^9 = 1000000000. Multiplying the nine divisors 1, 2, 4, 5, 10, 20, 25, 50 and 100 gives the same value.

Prove that d(n) is odd exactly when n is a perfect square. Hint: pair each divisor d with n / d.

Show the answer Divisors pair up as (d, n / d). A pair has two different members unless d = n / d, which means d is the square root of n. At most one divisor can equal the square root, so the total number of divisors is odd exactly when the square root is a whole number, which means n is a perfect square.

Find the smallest number from 1 to 10^6 with exactly 64 divisors. Hint: write a loop that uses the table and the divisor count, then keep the first number that matches.

Show the answer 7560. Its factorisation is 2^3 × 3^3 × 5 × 7, so the divisor count is 4 × 4 × 2 × 2 = 64. We scanned from 1 to 10^6 with the table and stopped at the first match. A brute force count for every number below 200 found no match there, which agrees with the scan.

Summary

Trial division factors one number in about the square root of its size, which is fine for one large number. A smallest prime factor table lets you factor many numbers in a few steps each. A factorisation gives the number of divisors as a product of exponents plus one, the divisor sum as a product of prime power sums, and the divisor product as a power of n. Most mistakes in this area are missing cases, such as the leftover prime, or wrong types, such as int where long long is needed.