3

我被要求将除 1 以外的因子和数组中每个数字的数字本身相加。问题是它必须能够处理具有非常大数字的非常大的数组，而我当前的实现对于大小为 100,000,000 的数组需要很长时间。我计算每个数字因素的代码是

static long countFactors(long num){
    long count=0;
    long max =(long) Math.floor(Math.sqrt(num));
    for(int i=2; i<=max;i++){
        if(num%i==0&&(i*i)!=num){
            // count i and n/i as a factor
            count+=2;
            if(num/i<max){
                max=num/i;
            }
        }            
        else if(num%i==0){
            // just add one factor since it is the numbers root.
            count+=1;

        }
    }

    return count;
}

有没有人有任何优化建议。

4

4 回答 4

2

很难回答这个问题，因为很难确切地知道问题是什么。一些评论如下。如果问题得到澄清，我可能会给出更好的答案。

1) 不清楚您是否想要数字n的不同质因数、具有多重性的质因数或数字的除数。例如，给定数n = 12，不同的质因数是 2 和 3，质因数及其重数是 2、2 和 3，除数是 1、2、3、4、6 和 12。你的程序回答了关于除数的问题，所以我假设这就是你想要的，但你也提到你想从列表中消除 1 和n，这是不寻常的。

2）在不同的时间你提到因素的计数和因素的总和。请准确说明您想要什么。

3) 不清楚您是在处理长度为 10^8 的数组还是与 10^8一样大的n数组。如果您的数组长度为 10^8，那么无论您做什么都需要一段时间。如果你有一个小得多的数组，比如一千个数字n，每个小于 10^8，这会变得简单得多。

假设您需要除数，这里有一个函数，它采用n的因子及其重数并返回n的除数的总和和计数；如果需要，您可以从计数中减去 2 并从总和中减去n +1 以排除 1 和n：

function divSumCount(n)
    mult, sum, count, prev := 2, 1, 1, 0
    for fact in sort(factors(n))
        if fact == prev
            mult := mult + 1
        else if prev <> 0
            sum := sum * (prev ** mult - 1) / (prev - 1)
            count := count * mult
            mult := 2
        prev := fact
    sum := sum * (prev ** mult - 1) / (prev - 1)
    count := count * mult
    return sum, count

这是伪代码，我将留给您翻译成 Java。假设n不大于 10^8，这是一个简单的程序，它使用试除法对n进行因子，返回按升序排序的因子；如果n较大，您将需要一个更好的算法来找到它的因子：

function factors(n)
    f, fs := 3, []
    while n % 2 == 0
        append 2 to fs
    while f * f <= n
        while n % f == 0
            append f to fs
            n := n / f
        f := f + 2
    if n > 1 append n to fs
    return fs

4）如果数字n在数组中是连续的，例如从 54813000 到 54823000，您可以筛选因子而不是费力地分解每个n，这样会快得多。

如果您需要更多，请告诉我。

于 2013-09-16T13:29:52.610 回答
2

我把最好的想法放在这篇文章的开头：

能被n整除的数能被 的所有因数整除n。

也许这是降低时间复杂度的关键。现在剩下的：

现在，您(i*i)!=num只需要执行一次即可执行 O(max) 次测试。（for(int i=2; i**<**max;i++)然后检查平方根）。你确实说了非常大的数字，所以这可以节省一点。

还有这是什么？ if(num/i<max){ max=num/i; }如果我没看错，这是多余的。这个循环中的因子永远不会i大于 的平方根num。

最后，在空间允许的情况下，您可以将外部循环i置于内部的数组中。这将节省一点点不需要重复i*i。这些只是对您当前算法的微优化。

于 2013-09-16T04:03:22.630 回答
0

CAVEAT EMPTOR：这是一个我没有用基准检查过的想法，所以它可能不是一个好的解决方案。

对于单个数字，您的代码非常好。但是如果你必须找到很多数字的因数，也许找到质因数是一个很好的解决方案。

我的想法是这样的

1）从列表中找到您必须处理的最大数字（最大值）。

2) 找到 1 和 max/2 之间的素数（这是困难的部分，但只做一次）。

3) 你把每个数分解成素数，vg 150 是 2*3*5*5

4）所有因子都是素因子的组合，在这种情况下它们是

*) 2

*) 2*3 = 6

*) 2*5 = 10

*) 2*3*5 = 30

*) 2*5^2 = 50

*) 3

*) 3*5 = 15

*) 3*5^2 = 75

*) 5

*) 5^2 = 25

优点是您只检查素数，它们只是数字的一部分（并且，如果您的数字变大，则减少一个）。缺点是计算非素数因子的最后一步，以及计算素数的时间（和内存）（尽管您可以预先计算它们并将它们存储在文件中以一定大小）。

于 2013-09-15T22:30:37.520 回答
0

我可能会后悔，但我会试一试。我假设您有足够的 RAM/swap 可用，并且更担心计算时间。我还假设您真的想要主要因素，而不是所有因素。

我要做的第一件事是对数组进行排序并确定唯一值。然后我会尝试使用一个数组来构建一个埃拉托色尼筛，sieve以识别所有素数，直到你的（排序的）唯一值数组中最大值的平方根。我还将所有数字的并行数组保持在最大值，调用它sum_array并将其初始化为全零。当我逐步遍历sieve数组以屏蔽当前值的所有倍数时，我还将逐步遍历sum_array相同的索引，并将当前素数添加到每个元素的运行总数中，同时屏蔽sieve数组中该素数的倍数。

因为我真的不知道这是为了什么，所以我已经没有关于除此之外做什么的建议了。

于 2013-09-15T23:08:50.303 回答