问题在适当的除数算法

我写了两个算法来得到一个给定的数字的正确除数的总和，找到完美的数字或丰富的数字。问题在适当的除数算法

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++) { 
     if (a % i == 0) 
      sum += i; 
    } 
    return sum; 
}

我认为他们都是正确的，第一个更快。但是我只能从第二个算法得到正确的结果。代码的其他部分是相同的。

有什么建议吗？在真实的工业编程中如何找到适当的因子？

在此先感谢。

来源

2011-09-02 darkjh

你认为** a **本身是一个除数吗？ –

你认为两者都是正确的，同时，只有第二个给出正确的结果？两者任一。 –

你的问题就在这里：

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

由于您将t从浮点数转换为int，因此它将四舍五入为整数值。这也假设t是实际的平方根，当它不是。当数字有因素x & x+1（我发布的单元测试以及i = 6，因为它的平方根是2.45和2是一个因子）失败时，这将评估为true。

支票真的应该是：

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

来源

2011-09-02 19:42:10

是的，这是解决问题......谢谢！ – darkjh

这里有一个简单的单元测试，我在C＃中写道，很快就会失效＃1中给出＃2是正确的：

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

太大评论...

来源

2011-09-02 19:34:01

Templatetypedef解决你的问题。然而，计算主要因素的最快可能方法是预先计算Eratostene筛子的所有素数因子（最大值为sqrt（MAX_INT）），将其存储到一个数组中，然后用它来分解数字a。这真的非常快。

来源

2011-09-02 19:48:22 Simone

这是一个老问题，但我正在浏览。

找到适当的除数之和有更快的算法。

使用Eratosthenes筛（或Atkin）筛选数字的主要因素。随着轮子因数分解，前100万个素数将需要30ms。

然后，所有的除数的总和是

For each n 

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

其中n是因子，米是因子的力量。

，例如，对于220 2^2 5 11的因素有

所以它的

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

这个总和ALL除数的总和，所以只减去Ñ

504-220 = 284

这应该比尝试所有的数字快得多，特别是如果你预先筛选并重新使用它。

来源

2013-04-19 10:22:20 Ronnie

问题在适当的除数算法

回答

相关问题