我正在使用Java BigInteger
类,并且对nextProbablePrime
方法背后的算法很好奇。我知道一些有效的素性测试算法,比如Miller-Rabin
,但不确定这里实现的是哪种算法。
尝试下面的代码,但仍然没有响应。
BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();
发布于 2019-06-24 23:31:40
我已经通过了BigInteger
的the source code。它在内部使用nextProbablePrime
方法的 algorithm。
发布于 2019-06-25 02:55:54
为什么你的例子一次又一次地运行而不返回:
你的数字有8200万位长,而且(根据素数)这样的素数大约是8200万/ log_e(2)的数字。所以你要求Miller-Rabin测试大约1500万个候选者,其中每个候选者涉及8200万比特,并且每个检查都不是微不足道的。所以,是的,即使像Miller-Rabin这样的高效算法也需要一段时间来处理如此大得令人难以置信的输入。
(我记得有一次跑步将一个数字提升到另一个数字,花费了太长的时间,并向语言开发人员抱怨他们应该使用重复平方来更快地求幂……在我退后一步并意识到我的测试号也有数百万位数字之前。)
https://stackoverflow.com/questions/56739468
复制相似问题