Algorithm to calculate the number of divisors of a given number

Question

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

User · Answer

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.

User · Answer

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 lt Integer gt  divisors n           ArrayList lt Integer gt  aList   new ArrayList        int top count    int  Math round Math sqrt n        int new n   n       for  int i   2  i  lt   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

User · Answer

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    amp  amp  printf   d is a divisor of  d n  i n      i lt   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   amp  amp   counter        i lt   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   amp  amp   counter        i lt   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   amp  amp   counter        i lt   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   amp  amp    n i   amp  amp   counter        i lt   n 2  i         return   counter      small is beautiful

User · Answer

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 lt stdio h gt   include lt math h gt  int main         int i n limit numberOfDivisors 1      printf  Enter the number           scanf   d   amp n       limit  int sqrt  double n       for i 2 i lt  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 lt  n i

User · Answer

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    general overview  http   en wikipedia org wiki Divisor function values for small n and some useful references  A000005  d n   also called tau n  or sigma 0 n    the number of divisors of n   real-world example  factorization of integers

User · Answer

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

User · Answer

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.

User · Answer

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  lt   m i          if n   i    0        count    2        if n   m    m  amp  amp  n   m    0      count--    return count

User · Answer

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

User · Answer

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  lt  limit    i            if  myNum   i    0                limit   myNum   i              if  limit    i                  divisorCount                divisorCount                        return divisorCount

User · Answer

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  lt  limit    i            if  x   i    0                limit   x   i              if  limit    i                    numberOfDivisors                              numberOfDivisors                         return numberOfDivisors

User · Answer

Number theory textbooks call the divisor-counting function tau  The first interesting fact is that it s multiplicative  ie  t ab    t a t 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  t p  k    k 1  the powers of p   Thus you can easily compute t 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   Test if the number is prime  fast  If so  return 2 Otherwise  factorise the number  slow if multiple large prime factors  Compute t n  from the factorisation

User · Answer

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

User · Answer

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 lt  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

User · Answer

This is an efficient solution    include  lt iostream gt  int main       int num   20     int numberOfDivisors   1     for  int i   2  i  lt   num  i            int exponent   0      while  num   i    0            exponent             num    i               numberOfDivisors     exponent 1          std  cout  lt  lt  numberOfDivisors  lt  lt  std  endl    return 0

User · Answer

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

User · Answer

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  lt  size  amp  amp  P i  lt  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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  lt  n          if n   i    0              count    2         i    1     if i    2    n          count    1     return count

User · Answer

i guess this one will be handy as well as precise   script pyton   gt  gt  gt factors   x for x in range  1 n 1  if n x  0  print len factors

User · Answer

You want the Sieve of Atkin  described here  http   en wikipedia org wiki Sieve of Atkin

User · Answer

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  lt  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

User · Answer

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

User · Answer

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  gt  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

User · Answer

This is something i came up with based on Justin answer  It might require some optimization   n int input     a    b     def sieve n       np   n   1     s   list range np        s 1    0     sqrtn   int n  0 5      for i in range 2  sqrtn   1            if s i               s i i  np  i     0    len range i i  np  i       return filter None  s   k list sieve n    for i in range len k            if n k i   0                  a append k i    a sort    for i in range len a            j 1         while n  a i   j   0                   j j 1         b append j-1   nod 1  for i in range len b            nod nod  b i  1   print  no of divisors of          format n nod

User · Answer

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  lt   n  and   z mod 12    1  or  z mod 12    5                prime z    not prime z           z   z-xx         if  z  lt   n  and  z mod 12    7               prime z    not prime z           z   z-yy-yy         if  z  lt   n  and  x  gt  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  lt   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

[performance] Algorithm to calculate the number of divisors of a given number

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

2 given L, calculate number of unique combinations

Examples related to performance

Examples related to algorithm

Examples related to pseudocode