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.

Answer 1

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

Answer 2

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 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 = 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 ain't it it's something similar me thinks.

Answer 3

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.

Answer 4

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

Answer 5

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...)

Answer 6

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: AOOOOO5: d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.

• real-world example: factorization of integers

Answer 7

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.

Answer 8

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.

Answer 9

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)

Answer 10

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.

Answer 11

Semicolon, that solution will not work. Let's try it for 20.

2**.5 == 4.47, so try up to five.

Primes up to five are 2, 5, multiply by 2 for a total of 4 divisors.

In reality, the divisors of 20 are 1,2,4,5,10,20, for a total of 6 divisors.

Answer 12

hi,my question is the following: how can i write a c++ code that will read anumber from the user and display all the positive divisors of that number in a decresing order. for more information i'm studing know c++ in case if the question was stuped>.< thanks any way.

Answer 13

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