本文介绍了什么是最快的分解算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

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:

  • 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

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

08-03 22:00