182

What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number?

It'll be great if you could provide pseudocode or a link to some example.

EDIT: All the answers have been very helpful, thank you. I'm implementing the Sieve of Atkin and then I'm going to use something similar to what Jonathan Leffler indicated. The link posted by Justin Bozonier has further information on what I wanted.

4
  • Given your reqs coming up with the number of factors is vague. I'm guessing you are looking for the number of non-unique prime divisors because if you didn't want that I code just write a program to always return 1 if the number to factor is one and 2 if it's anything else. 0 might need a change... Sep 21, 2008 at 6:09
  • @sker: Is there a range of Values for which you need the divisors. There are many ways of calculating the factors, and each method is better suited to a particular range. Oct 30, 2008 at 10:53
  • 2
    Here is a related interesting problem projecteuler.net/problem=12
    – daniloquio
    Jan 6, 2012 at 20:10
  • 1
    The naive Sieve of Atkin even from the edited Wikipedia article will never be faster than a maximally wheel factorized Sieve of Eratosthenes up to huge impractical limits, and the page segmented versions are even in more favour of the SoE (see SoE primesieve versus SoA primegen as implemented by Atkin's partner Bernstein. It is common incorrect Internet knowledge that the their study proved SoA faster, but they artificially limited the optimization of the SoE used in order to prove this. See my SoA answer for further explanation Apr 3, 2015 at 4:52

26 Answers 26

77

Dmitriy is right that you'll want the Sieve of Atkin to generate the prime list but I don't believe that takes care of the whole issue. Now that you have a list of primes you'll need to see how many of those primes act as a divisor (and how often).

Here's some python for the algo Look here and search for "Subject: math - need divisors algorithm". Just count the number of items in the list instead of returning them however.

Here's a Dr. Math that explains what exactly it is you need to do mathematically.

Essentially it boils down to if your number n is:
n = a^x * b^y * c^z
(where a, b, and c are n's prime divisors and x, y, and z are the number of times that divisor is repeated) then the total count for all of the divisors is:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, to find a,b,c,etc you'll want to do what amounts to a greedy algo if I'm understanding this correctly. Start with your largest prime divisor and multiply it by itself until a further multiplication would exceed the number n. Then move to the next lowest factor and times the previous prime ^ number of times it was multiplied by the current prime and keep multiplying by the prime until the next will exceed n... etc. Keep track of the number of times you multiply the divisors together and apply those numbers into the formula above.

Not 100% sure about my algo description but if that isn't it it's something similar .

7
  • 1
    If you're factoring a large number, you don't even want to have to look at the prime list. You want to eliminate whole ranges of possibilities as quickly as possible! See my answer for more.
    – user11318
    Sep 21, 2008 at 9:33
  • I realize this was 2 years ago, but your python algo link is broken, happen to know where it exists now?
    – jb.
    Apr 1, 2011 at 6:19
  • 2
    So n = (a^x * b^y * c^z)-(x + 1) * (y + 1) * (z + 1) is the rule
    – Learner
    May 15, 2016 at 7:53
  • 1
    As @Shashank says, the algorithm in the "EDIT:" section is wrong: Suppose n = 45 = 3*3*5. The largest prime divisor is 5, but multiplying this by itself until it exceeds n would cause the algorithm to report that it has 2 copies of the factor 5 (since 5*5 = 25 < 45). Jun 15, 2016 at 15:00
  • 1
    The 'Sieve of Atkin' has a runtime complexity of O(N / log(log(N))) at best. Brute-force checking all possible divisors from 1 ... Sqrt(n) has a runtime complexity of O(Sqrt(N)) which is far superior. How come this answer has been accepted?
    – le_m
    Mar 13, 2017 at 15:57
48

There are a lot more techniques to factoring than the sieve of Atkin. For example suppose we want to factor 5893. Well its sqrt is 76.76... Now we'll try to write 5893 as a product of squares. Well (77*77 - 5893) = 36 which is 6 squared, so 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71. If that hadn't worked we'd have looked at whether 78*78 - 5893 was a perfect square. And so on. With this technique you can quickly test for factors near the square root of n much faster than by testing individual primes. If you combine this technique for ruling out large primes with a sieve, you will have a much better factoring method than with the sieve alone.

And this is just one of a large number of techniques that have been developed. This is a fairly simple one. It would take you a long time to learn, say, enough number theory to understand the factoring techniques based on elliptic curves. (I know they exist. I don't understand them.)

Therefore unless you are dealing with small integers, I wouldn't try to solve that problem myself. Instead I'd try to find a way to use something like the PARI library that already has a highly efficient solution implemented. With that I can factor a random 40 digit number like 124321342332143213122323434312213424231341 in about .05 seconds. (Its factorization, in case you wondered, is 29*439*1321*157907*284749*33843676813*4857795469949. I am quite confident that it didn't figure this out using the sieve of Atkin...)

3
  • 1
    You're technique is very clever, but it doesn't tell me how many factors does the number have, does it?
    – sker
    Sep 21, 2008 at 18:09
  • 23
    Once you have the prime factorization, figuring out how many factors there are is straightforward. Suppose the prime factors are p1, p2, ..., pk and they are repeated m1, m2, ..., mk times. Then there are (1+m1)(1+m2)...(1+mk) factors.
    – user11318
    Sep 21, 2008 at 20:59
  • An interesting sieve is the quadratic sieve. This uses number theory - quadratic congruences, and some linear algebra. I learned enough to use it in a 2nd year number theory course at university.
    – Tanner
    Nov 24, 2012 at 4:28
35

@Yasky

Your divisors function has a bug in that it does not work correctly for perfect squares.

Try:

int divisors(int x) {
    int limit = x;
    int numberOfDivisors = 0;

    if (x == 1) return 1;

    for (int i = 1; i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            if (limit != i) {
                numberOfDivisors++;
            }
            numberOfDivisors++;
        }
    }

    return numberOfDivisors;
}
2
  • 6
    Won't (x % i) cause a divide by zero when i = 0? should i = 1..limit ?
    – rhu
    Jun 27, 2012 at 21:03
  • @rhu Checking 0 is pointless anyway because 0 isn't a factor of any number. Feb 13, 2019 at 20:55
30

I disagree that the sieve of Atkin is the way to go, because it could easily take longer to check every number in [1,n] for primality than it would to reduce the number by divisions.

Here's some code that, although slightly hackier, is generally much faster:

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

ps That's working python code to solve this problem.

15

Here is a straight forward O(sqrt(n)) algorithm. I used this to solve project euler

def divisors(n):
    count = 2  # accounts for 'n' and '1'
    i = 2
    while i ** 2 < n:
        if n % i == 0:
            count += 2
        i += 1
    if i ** 2 == n:
        count += 1
    return count

5
  • but why do you always increase the count by 2?...is there a theorem you applied?
    – SummerCode
    May 11, 2015 at 8:53
  • 3
    because you are conting only until sqrt(n). For eg: if you are trying to find all divisors for 36 - you will count from 2 to 6. You know that 1&36,2&18, 3&12, 4&9, 6,6 are all divisors and they come in pairs. May 11, 2015 at 21:31
  • 2
    thanks a lot Anthony, i understood now :D! a small addendum: i think it should treat the sqrt(n) value separately because for now it takes it into consideration two times instead of one, i think
    – SummerCode
    May 12, 2015 at 7:23
  • While O(sqrt(n)) is not too bad, it is not optimal. computing the prime factor decomposition can be done much faster and is sufficient to compute the number of divisors.
    – le_m
    Mar 13, 2017 at 17:09
  • At each iteration, you have to calculate i², wouldn't it be faster to compare i with √n (calculated only once)?
    – Yukulélé
    Apr 13, 2020 at 18:29
11

This interesting question is much harder than it looks, and it has not been answered. The question can be factored into 2 very different questions.

1 given N, find the list L of N's prime factors

2 given L, calculate number of unique combinations

All answers I see so far refer to #1 and fail to mention it is not tractable for enormous numbers. For moderately sized N, even 64-bit numbers, it is easy; for enormous N, the factoring problem can take "forever". Public key encryption depends on this.

Question #2 needs more discussion. If L contains only unique numbers, it is a simple calculation using the combination formula for choosing k objects from n items. Actually, you need to sum the results from applying the formula while varying k from 1 to sizeof(L). However, L will usually contain multiple occurrences of multiple primes. For example, L = {2,2,2,3,3,5} is the factorization of N = 360. Now this problem is quite difficult!

Restating #2, given collection C containing k items, such that item a has a' duplicates, and item b has b' duplicates, etc. how many unique combinations of 1 to k-1 items are there? For example, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} must each occur once and only once if L = {2,2,2,3,3,5}. Each such unique sub-collection is a unique divisor of N by multiplying the items in the sub-collection.

2
  • Here is a link to some pseudo code for a problem very similar to 2. answers.google.com/answers/threadview/id/392914.html
    – mR_fr0g
    May 9, 2011 at 20:25
  • 5
    Question #2 has a well known solution. For a factorization of { p_i, k_i } where p_i is a prime factor of a number with k_i multiplicity, the total number of divisors of that number is (k_1+1)*(k_2+1)*...*(k_n+1). I guess you know this by now but I write this down for the benefit if a random reader here.
    – Will Ness
    Sep 6, 2012 at 16:20
10

An answer to your question depends greatly on the size of the integer. Methods for small numbers, e.g. less then 100 bit, and for numbers ~1000 bit (such as used in cryptography) are completely different.

7

JUST one line
I have thought very carefuly about your question and I have tried to write a highly efficient and performant piece of code To print all divisors of a given number on screen we need just one line of code! (use option -std=c99 while compiling via gcc)

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

for finding numbers of divisors you can use the following very very fast function(work correctly for all integer number except 1 and 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

or if you treat given number as a divisor(work correctly for all integer number except 1 and 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

NOTE:two above functions works correctly for all positive integer number except number 1 and 2 so it is functional for all numbers that are greater than 2 but if you Need to cover 1 and 2 , you can use one of the following functions( a little slower)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

OR

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

small is beautiful :)

6

The sieve of Atkin is an optimized version of the sieve of Eratosthenes which gives all prime numbers up to a given integer. You should be able to google this for more detail.

Once you have that list, it's a simple matter to divide your number by each prime to see if it's an exact divisor (i.e., remainder is zero).

The basic steps calculating the divisors for a number (n) are [this is pseudocode converted from real code so I hope I haven't introduced errors]:

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z
0
6

You might try this one. It's a bit hackish, but it's reasonably fast.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
3
  • 2
    While this function provides a prime factor decomposition of n in reasonable time, it is a) not optimal and b) does not calculate the number of divisors of a given number as per OP's question
    – le_m
    Mar 13, 2017 at 17:05
  • And won't work for big numbers because of its recursion Feb 25, 2018 at 6:43
  • Though this is not optimal, and rather than counting factors, it actually lists them, the simplicity and beauty of this is amazing and is reasonably fast. ^^ May 4, 2018 at 7:31
5

Once you have the prime factorization, there is a way to find the number of divisors. Add one to each of the exponents on each individual factor and then multiply the exponents together.

For example: 36 Prime Factorization: 2^2*3^2 Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36 Number of Divisors: 9

Add one to each exponent 2^3*3^3 Multiply exponents: 3*3 = 9

4

Before you commit to a solution consider that the Sieve approach might not be a good answer in the typical case.

A while back there was a prime question and I did a time test--for 32-bit integers at least determining if it was prime was slower than brute force. There are two factors going on:

1) While a human takes a while to do a division they are very quick on the computer--similar to the cost of looking up the answer.

2) If you do not have a prime table you can make a loop that runs entirely in the L1 cache. This makes it faster.

4

This is an efficient solution:

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}
2

You want the Sieve of Atkin, described here: http://en.wikipedia.org/wiki/Sieve_of_Atkin

4
  • 1
    That's going to get you the primes below your given number - but there's not guarantee that those primes are going to be divisors? (unless I'm missing something) Sep 21, 2008 at 6:05
  • It's a quick leap from here to finding all primes < sqrt(N) that evenly divide N.
    – SquareCog
    Sep 21, 2008 at 6:17
  • 1
    It may be a quick leap, but testing all primes < sqrt(N) is still a bad factoring technique no matter how efficiently you find them. There are a lot of ways to improve that.
    – user11318
    Sep 21, 2008 at 8:49
  • Testing the primes is O(N), it's finding the primes that's the hard part. But with even with the unoptimised sieve of eratosthenes, you can still find all primes under a few million in under a second. That covers any 64b number, and I'm sure we're not talking about factoring crypto level stuff here Oct 6, 2008 at 8:00
2

Divisors do something spectacular: they divide completely. If you want to check the number of divisors for a number, n, it clearly is redundant to span the whole spectrum, 1...n. I have not done any in-depth research for this but I solved Project Euler's problem 12 on Triangular Numbers. My solution for the greater then 500 divisors test ran for 309504 microseconds (~0.3s). I wrote this divisor function for the solution.

int divisors (int x) {
    int limit = x;
    int numberOfDivisors = 1;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            numberOfDivisors++;
        }
    }

    return numberOfDivisors * 2;
}

To every algorithm, there is a weak point. I thought this was weak against prime numbers. But since triangular numbers are not print, it served its purpose flawlessly. From my profiling, I think it did pretty well.

Happy Holidays.

6
  • 1
    You'd have a divide by 0 on the first iteration here
    – barfoon
    Aug 19, 2011 at 16:31
  • unfortunately not. the ++i is different from i++ (which would result in a divide-by-zero error)
    – Igbanam
    Sep 23, 2011 at 8:53
  • I wrote your function in PHP and ran it - here's what I got - i.minus.com/iKzuSXesAkpbp.png
    – barfoon
    Sep 23, 2011 at 14:48
  • for some weird reason, this worked flawlessly for me. oh well, my bad. start numberOfDivisors and the iterator at 1; this should get rid of the divide by zero error
    – Igbanam
    Oct 21, 2011 at 10:57
  • 1
    Your algorithm doesn't work for perfect squares. For example, it returns 4 for the input x = 4, because it is counting 2 twice...1, 2, 2, 4. Answer should be 3: 1,2,4
    – Michael
    Jan 24, 2012 at 18:48
2

Number theory textbooks call the divisor-counting function tau. The first interesting fact is that it's multiplicative, ie. τ(ab) = τ(a)τ(b) , when a and b have no common factor. (Proof: each pair of divisors of a and b gives a distinct divisor of ab).

Now note that for p a prime, τ(p**k) = k+1 (the powers of p). Thus you can easily compute τ(n) from its factorisation.

However factorising large numbers can be slow (the security of RSA crytopraphy depends on the product of two large primes being hard to factorise). That suggests this optimised algorithm

  1. Test if the number is prime (fast)
  2. If so, return 2
  3. Otherwise, factorise the number (slow if multiple large prime factors)
  4. Compute τ(n) from the factorisation
2

This is the most basic way of computing the number divissors:

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}
1

the prime number method is very clear here . P[] is a list of prime number less than or equal the sq = sqrt(n) ;

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .
1

The following is a C program to find the number of divisors of a given number.

The complexity of the above algorithm is O(sqrt(n)).

This algorithm will work correctly for the number which are perfect square as well as the numbers which are not perfect square.

Note that the upperlimit of the loop is set to the square-root of number to have the algorithm most efficient.

Note that storing the upperlimit in a separate variable also saves the time, you should not call the sqrt function in the condition section of the for loop, this also saves your computational time.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

Instead of the above for loop you can also use the following loop which is even more efficient as this removes the need to find the square-root of the number.

for(i=2;i*i<=n;i++)
{
    ...
}
1

Here is a function that I wrote. it's worst time complexity is O(sqrt(n)),best time on the other hand is O(log(n)). It gives you all the prime divisors along with the number of its occurence.

public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}
1
  • I don't know what this function computes, but it definitely is not the list of divisors of n.
    – le_m
    Mar 13, 2017 at 15:48
1

@Kendall

I tested your code and made some improvements, now it is even faster. I also tested with @هومن جاویدپور code, this is also faster than his code.

long long int FindDivisors(long long int n) {
  long long int count = 0;
  long long int i, m = (long long int)sqrt(n);
  for(i = 1;i <= m;i++) {
    if(n % i == 0)
      count += 2;
  }
  if(n / m == m && n % m == 0)
    count--;
  return count;
}
0

Isn't this just a question of factoring the number - determining all the factors of the number? You can then decide whether you need all combinations of one or more factors.

So, one possible algorithm would be:

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

It is then up to you to combine the factors to determine the rest of the answer.

0
0

I think this is what you are looking for.I does exactly what you asked for. Copy and Paste it in Notepad.Save as *.bat.Run.Enter Number.Multiply the process by 2 and thats the number of divisors.I made that on purpose so the it determine the divisors faster:

Pls note that a CMD varriable cant support values over 999999999

@echo off

modecon:cols=100 lines=100

:start
title Enter the Number to Determine 
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done  it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.

set /p number=Enter Number : 
if %number% GTR 999999999 goto start

echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%

:Determining

set /a mindet=%mindet%+1

if %mindet% GTR %B% goto Results

set /a solution=%number% %%% %mindet%

if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1

set /a B=%number% / %mindet%

set /a procent=%mindet%*100/%B%

if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%

title Progress : %procent% %%%



if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining

:Results

title %proces% Results Found
echo.
@pause
goto start
1
  • 882161280 - 1282 divisors
    – dondon
    Feb 7, 2016 at 22:49
0

i guess this one will be handy as well as precise

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

0

Try something along these lines:

int divisors(int myNum) {
    int limit = myNum;
    int divisorCount = 0;
    if (x == 1) 
        return 1;
    for (int i = 1; i < limit; ++i) {
        if (myNum % i == 0) {
            limit = myNum / i;
            if (limit != i)
                divisorCount++;
            divisorCount++;
        }
    }
    return divisorCount;
}
-1

I don't know the MOST efficient method, but I'd do the following:

  • Create a table of primes to find all primes less than or equal to the square root of the number (Personally, I'd use the Sieve of Atkin)
  • Count all primes less than or equal to the square root of the number and multiply that by two. If the square root of the number is an integer, then subtract one from the count variable.

Should work \o/

If you need, I can code something up tomorrow in C to demonstrate.

1
  • 3
    I'm confused. Counting all the primes less than the square root of a number will not give you it's divisors... not every prime less than the square root of a number will be a divisor for that number. Aug 2, 2011 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.