简单快速的随机素数发生器？

Question

我知道有许多素数发生器，比如Eratosthenes的筛子或Atkin。但它们从小数字开始依次生成数字。在不从小数开始的情况下，我可以用什么方法在间隔内得到素数？

一种选择可以是使用随机数生成器，并根据我想要实现的目标，使用素数测试、确定性测试或概率测试来测试输出。无论如何，测试将是缓慢而复杂的。

有没有一种快速简便的方法来生成非连续素数？假冒伪劣发生器也可以。

问候

我把这个问题改写得更清楚了：

我怎样才能在给定的间隔内生成素数，而不需要：--从小到最大的质数(如Erathostenes筛网)--也不能对随机序列使用缓慢的概率素数检验？

是否有任何快速和简单的算法或函数，以这样的方式产生数字，如果你运行它很长时间，你得到一个区间内的所有素数？(我不介意它是否也会生成一些合成物)。

Answer 1

如果间隔不是太大，低端也不是太高，你可以使用一个分割的埃拉托斯提尼筛子；“太大”和“太高”的定义取决于你的抱负和耐心，但任何大于10^15的东西都不太可能成功。否则，您可以在所需的间隔中选择一个随机奇数，测试它是否为素数，如果它是素数，或者尝试下一个较大的奇数，直到找到一个素数为止；如果您愿意，可以通过使用素轮生成候选素数来加快速度，而不仅仅是测试下一个奇数。没有第三种选择。

你已经说过，如果这个数字是合成的，你不会太在意。在这种情况下，你可以生成一个随机奇数，测试它是否有强的伪随机性到基2，而没有其他基，如果测试表明它是素数，或者用下一个奇数再试一次，如果测试表明它是复合的。这不是一个完美的原始性测试，但它比对Miller-Rabin测试做25次随机碱基测试更快，也比卢卡斯伪随机测试更快，而且可能对您的目的来说足够好。

您可以通过在堆栈溢出处搜索，或者通过查看我的博客来找到对所有这些事情的描述，或者您可以在这里询问是否有其他特定的问题。