什么是最快的整数分解算法

什么是最快的整数分解算法

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

问题描述

我编写了一个程序,试图找到可配对.这需要找到适当的数字除数之和.

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

这是我当前的sumOfDivisors()方法:

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;
}

因此,我需要进行很多分解,并且这已开始成为我应用程序中的真正瓶颈.我在MAPLE中键入了一个巨大的数字,并且把它迅速地分解了.

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