素数问题

Question

我正在尝试编写一个程序,以找到一个非常大的最大素数因子,并尝试了几种不同的成功方法.到目前为止我发现的所有这些都令人难以置信地缓慢.我有一个想法,我想知道这是否是一个有效的方法:

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

这种方法需要输入,并将执行以下操作:

200 - > 100 - > 50 - > 25 - > 5(返回)

90 - > 45 - > 15 - > 5(返回)

它将currentNum重复除以最小的可分数(最常见的是2或3),直到currentNum本身为素数(没有可分的素数小于currentNum的平方根),并假设这是原始输入的最大素数因子.

这会一直有效吗？如果没有,有人可以给我一个反例吗？

-

编辑:非常大,我的意思是大约2 ^ 40,或10 ^ 11.

Answer 1

该方法可行,但速度很慢."你的数字有多大？" 确定使用方法:

• 小于2 ^ 16左右:查找表.
• 不到2 ^ 70左右:阿特金的筛子.这是更着名的Eratosthenes筛子的优化版本. 编辑: 理查德·布伦特的修改的波拉德的RHO算法可能是在这种情况下更好.
• 小于10 ^ 50:Lenstra椭圆曲线分解
• 小于10 ^ 100:二次筛
• 超过10 ^ 100:General Number Field Sieve

Answer 2

由于Unique Prime Factorization定理,这将始终有效.