How do you count the factors of large integers? You could go from 1 up to N trying to divide it for all numbers in between, but this wouldn’t be very efficient.

A better approach is to use only the prime factors of a number, as all other factors can be derived from those. In fact all you have to do is to find the exponent of each prime factor of a number, add 1 to all of them, and multiply the result to get the total number of factors.

For example, say we want to find the number of factors of 12. 12 is equal to 2*2*3 in prime factors, so 2^2 * 3^1. The exponents are 2 and 1. Adding one to both we get 3 and 2, so 12 has 3*2 factors, which is 6. They are:

1,2,3,4,6,12

Below you’ll find the algorithm to compute the number of factors of any number. Just keep in mind that you might need to increase the size of the primes array if the number you are working with is very large.

#include <iostream>
int primes[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};

int nFactors (unsigned long long int n){
    int i;
    int factors[20] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    int result = 1;

    for (i=0;i<20;i++){
        while (n%primes[i]==0){
            factors[i]++;
            n/=primes[i];
        }
    }

    for (i=0;i<20;i++)
        result *= factors[i];

    return result;
}

int main(){

    cout << nFactors(210) << endl;

    return 0;
}