我正在实施 Eratosthenes 筛,对此的解释请参见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。但是我想调整它来生成 M 个素数,而不是从 1 到 N 的素数。我这样做的方法是简单地创建一个足够大的 N,以便所有 M 个素数都包含在这个范围内。有没有人有任何好的启发式来模拟素数的增长?如果您希望发布代码片段,我将在 Java 和 C++ 中实现它。
问问题
686 次
5 回答
3
第 n 个素数的近似值取自维基百科;因此你只需要分配一个数组m*log(m)+m*log(log(m))
;一个数组m*log(m)
将是不够的。
于 2011-09-26T18:51:23.493 回答
1
另一种选择是分段筛。将数字筛选到一百万。然后是第二个百万。然后是第三个。等等。当你有足够的时候停下来。
为下一段重新设置筛子并不难。有关详细信息,请参阅我的博客。
于 2011-09-26T19:49:08.663 回答
0
为什么不动态增长筛子?每当您需要更多素数时,重新分配筛选内存,并使用您之前找到的素数在新空间上运行筛选算法。
于 2011-09-26T18:23:49.767 回答
0
想到惰性求值(例如 Haskell 和其他函数式语言为您做)。尽管您使用命令式语言写作,但您可以应用我认为的概念。
考虑从候选集中删除剩余基数的操作。无需实际接触真正的算法(更重要的是无需猜测您将创建多少个数字),以惰性方式执行此操作(您必须实现,因为您使用的是命令式语言),何时以及是否尝试取最小的剩余数。
于 2011-09-26T19:11:32.617 回答