Divisors and Divisor Functions

Prime powers turn divisor enumeration into independent exponent choices. If n=p₁^e₁…pₖ^eₖ, any positive divisor chooses each prime’s exponent from zero through its exponent in n. This gives formulas for the number and sum of divisors, while an iterative construction lists the divisors themselves. These tools appear in factor constraints, multiplicative functions and arithmetic counting problems.

Prerequisites: Prime Factorization; vectors and sorting.

Build the idea

1. 1. Describe every divisor uniquely

   For each prime power pᵉ in n, a divisor contains p⁰,p¹,…,pᵉ. Choices for different primes are independent and uniquely determine the divisor. Therefore the number of choices multiplies. For n=12=2²·3¹, there are 3×2=6 divisors.

   $$\tau \left(n\right)=\prod (e_i+1)$$

2. 2. Derive the divisor sum

   Expanding ∏(1+p+…+pᵉ) chooses one power from every factor, so each divisor appears exactly once. The geometric-series closed form is (p^(e+1)−1)/(p−1), but computing p^(e+1) can overflow even if another representation is safe. The program accumulates the short geometric sum by multiplying successive powers instead.

   $$\sigma \left(n\right)=\prod (1+p+\dots +p^e)$$

3. 3. Generate without duplicates

   Begin with divisors=[1]. For the next prime p with exponent e, snapshot the old list size. For each power p¹..pᵉ append oldDivisor·power for every OLD divisor. Keep the old entries for exponent zero. Do not iterate over newly appended entries in the same prime stage: that would repeat exponents beyond e. Distinct prime-exponent choices guarantee no duplicate divisors.

4. 4. Trace n=12

   Starting [1], the 2² stage adds 2 and 4, giving [1,2,4]. The 3 stage adds [3,6,12]. Sorting yields [1,2,3,4,6,12]. Count is 6 and sum is (1+2+4)(1+3)=7·4=28. For n=1 no prime stage runs, leaving one divisor 1 with both count and sum equal to one.

5. 5. Separate factoring from output

   Factorization costs can dominate a small divisor list. Once factors are known, constructing and printing τ(n) divisors necessarily needs at least that many outputs. A method returning only τ or σ avoids storing the full list. For very large n or modular versions, analyze products and division separately; the ordinary geometric quotient is not automatically valid modulo a composite modulus.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Separate factoring from output Factorization costs can dominate a small divisor list.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
int main(){
    long long n;
    std::cin>>n;
    long long remaining=n;
    std::vector<std::pair<long long,int>>factors;
    for(long long p=2;p<=remaining/p;++p){
        if(remaining%p==0){
            int e=0;
            do{
                remaining/=p;
                ++e;
            }
            while(remaining%p==0);
            factors.push_back({p,e});
        }
    }
    if(remaining>1){
        factors.push_back({remaining,1});
    }
    std::vector<long long>divisors{1};
    long long count=1,sum=1;
    for(auto[p,e]:factors){
        int oldSize=(int)divisors.size();
        long long power=1,geometric=1;
        for(int exponent=1;exponent<=e;++exponent){
            power*=p;
            geometric+=power;
            for(int i=0;i<oldSize;++i){
                divisors.push_back(divisors[i]*power);
            }
        }
        count*=e+1;
        sum*=geometric;
    }
    std::sort(divisors.begin(),divisors.end());
    std::cout<<count<<' '<<sum<<'\n';
    for(int i=0;i<(int)divisors.size();++i){
        std::cout<<divisors[i]<<(i+1==(int)divisors.size()?'\n':' ');
    }
}

Complexity analysis

O(√n + τ(n) log τ(n)) time including trial factorization and sorting. Building the list takes O(τ(n)) generated entries, while count/sum use O(log n) prime-power operations. O(τ(n)+log n) memory is a safe total bound. n≤10^12 ensures every divisor≤n and σ(n)≤n·τ(n)≤2n√n≤2×10^18, within long long.

Example input and output

Read n in 1..10^12. Print divisor count and divisor sum, then all positive divisors in increasing order.

Input

12

Output

6 28
1 2 3 4 6 12

Prime powers 2² and 3 give (2+1)(1+1)=6 divisors and (1+2+4)(1+3)=28 total.

Practical applications

Use for enumerating factor candidates, counting ways to choose divisors and evaluating multiplicative arithmetic functions. If only one divisibility test is needed, a remainder is simpler. For many small values, sieve-style divisor counts may be faster than factoring each independently.

Check your understanding

Why does pᵉ contribute e+1 divisor choices?

Put it into practice

Compute the number of perfect-square divisors from the factor exponents.