分段阿特金的筛，可能吗？ [英] Segmented Sieve of Atkin, possible?

问题描述

我知道的事实，即埃拉托塞尼的筛可以被实现，使得它发现素数时间可持续没有一个上限（分段筛）

I am aware of the fact that the Sieve of Eratosthenes can be implemented so that it finds primes continuosly without an upper bound (the segmented sieve).

我的问题是，可能阿特金/伯恩斯坦的筛以同样的方式来实现？

My question is, could the Sieve of Atkin/Bernstein be implemented in the same way?

相关问题： C＃：如何让阿特金的筛增量

然而，相关的问题只有1个答案，其中说，这是不可能的所有筛子，这显然是不正确。

However the related question has only 1 answer, which says "It's impossible for all sieves", which is obviously incorrect.

推荐答案

阿特金/伯恩斯坦给出一个分段的版本在他们的原件。 presumably伯恩斯坦的 primegen 计划使用该方法。

Atkin/Bernstein give a segmented version in Section 5 of their original paper. Presumably Bernstein's primegen program uses that method.

这篇关于分段阿特金的筛，可能吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！