质数问题


问题内容

我正在尝试编写一个程序来查找非常大的最大素数,并且尝试了几种方法,但均获得了不同的成功。到目前为止,我发现的所有速度都令人难以置信。我有一个想法,想知道这是否是一种有效的方法:

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。


问题答案:

由于唯一的素因式分解定理,这将始终有效。