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