Problem in proper divisor algo

I wrote two algos to get the sum of the proper divisors of a given number,to find perfect number or abundant number.

long sum_divisors_1(int a)
{
    int i, t;
    long sum = 1;
    for (i = 2, t = sqrt(a); i < t + 1; i++) {
        if (a % i == 0) {
            sum += i;
            sum += a / i;
        }
    }
    if (a % t == 0)
    sum -= t;
    return sum;
}

long sum_divisors_2(int a)
{
    int i, sum;
    sum = 0;
    for (i = 1; i < (int) (a / 2 + 1); i++) {
开发者_StackOverflow社区        if (a % i == 0)
            sum += i;
    }
    return sum;
}

And I think they are both correct and the first one is faster. But I can only get the correct result from the second algo. Other parts of the code are the same.

Any suggestions? And how the proper divisors are found in real industrial programming?

Thanks in advance.

---

Your problem lies here:

if (a % t == 0)
    sum -= t;

Since you're casting t to an int from a floating point, it will round down to an integer value. This also assumes that t is the actual square root when it isn't. This will evaluate to true when a number has factors x & x+1 (the unit test I posted as well fails when i = 6 because it's square root is 2.45 and 2 is a factor).

The check really should be:

if (t*t == a)
    sum -= t;

---

This is an old question but I was browsing.

There's a much faster algorithm to find the sum of proper divisors.

Find the prime factors of a number using Sieve of Eratosthenes (or Atkin). With wheel factorisation the first 1m prime numbers will take maybe 30ms.

Then the sum of all divisors is

For each n

    sum += (n ^ (m+1) - 1) / (n-1)

where n is the factor, m is the power of that factor.

Eg for 220 2^2 5 11 are the factors

So it's sum of

2 ^ (2+1) - 1 / 1 *
5 ^ (1+1) - 1 / 4 *
11 ^ (1+1) - 1 / 10  
= 7 * 6 * 12
= 504

This is the sum of ALL divisors, so just subtract N

504-220 = 284

This should be a lot faster than trying all the numbers, especially if you precalculate the sieve and reuse it.

---

Here's a simple unit test I wrote in C# that will quickly invalidate #1 given #2 is correct:

for(int i = 4; i < 28124; i++)
{
    Assert.AreEqual(sum_divisors_2(i), sum_divisors_1(i), "Failed when i = {0}", i);
}

Too big for a comment...

---

Templatetypedef solved your problem; however the fastest possible way to compute the prime factors is to precompute all the prime factors up to sqrt(MAX_INT) with Eratostene sieve, store it into an array and then use it to factorize the number a. This is really really really much faster.