什么是最快的分解算法？ [英] What is the fastest factorization algorithm?

问题描述

我已经写了一个程序，试图寻找友善对。这就需要找到号码的适当除数的总和。

I've written a program that attempts to find Amicable Pairs. This requires finding the sums of the proper divisors of numbers.

下面是我目前的sumOfDivisors（）方法：

Here is my current sumOfDivisors() method:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

所以，我需要做大量分解，并已开始成为我的应用程序真正的瓶颈。我输入数量庞大到枫树和它分解它出奇的快。

So I need to do lots of factorization and that is starting to become the real bottleneck in my application. I typed a huge number into MAPLE and it factored it insanely fast.

什么是更快的分解算法之一？

What is one of the faster factorization algorithms?

推荐答案

该方法将工作，但将是缓慢的。 有多大的数字？决定了使用的方法：

Pulled directly from my answer to this other question.

The method will work, but will be slow. "How big are your numbers?" determines the method to use:

• 在小于2 ^ 16左右：查找表
• 在小于2 ^ 70左右：的的理查德·布伦特的修改 = http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm">Pollard's RHO算法。
• 在不到10 ^ 50：伦斯特拉椭圆曲线分解
• 在小于10 ^ 100：二次筛
• 在超过10 ^ 100：一般数域筛

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Richard Brent's modification of Pollard's rho algorithm.
• Less than 10^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve

这篇关于什么是最快的分解算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！