c - 埃拉托色尼分段筛算法

Question

我正在尝试解决 spoj 上的“PRIME1”(http://www.spoj.com/problems/PRIME1/)。很多人说我应该使用埃拉托色尼分段筛来解决它。我了解埃拉托色尼筛，但我如何实现分段筛？我已经看过所有的资源，但无法正确理解。这是我为埃拉托斯特尼筛法编写的代码:

#include<stdio.h>
#include<math.h>
int main()
{
    long long int i,n,j,m;
    _Bool a[10000];
    scanf(" %lld",&n);
    for(i=2;i<=n;i++)
    {
        a[i]=1;
    }
    for(i=2;i<=sqrt(n);i++)
    {
        for(j=2;i*j<=n;j++)
        {
            a[i*j]=0;
        }
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==1)
            printf("%lld\n",i);
    }
  return 0;
}

由此，我如何实现埃拉托色尼分段筛。请从初学者的角度解释一下。

Answer 1

这个想法非常简单:

• 从k=2开始
• 计算输入区间后您将落入的位置；这就是x=((m + k - 1)/k)*k 。例如 m=12345和k=7你得到 12348，这是大于或等于 m 的 7 的最小倍数.
• 标记与 x 相关的位置为“已采取”并继续添加 k至x直到你通过n
• 增量k并重复直到您通过sqrt(n)

您无需测试 k 的所有值但仅限素数。为此，您可以使用普通筛来计算所有不大于 sqrt(n) 的素数。 (请注意，sqrt(1000000000) < 31623 并不是一个很大的数字，该范围内只有 3401 个素数)。

注意不要“标记”x在内循环开始时如果它恰好等于 k ; x 要考虑的最小值是 2*k .

您可以停在sqrt(n)而不是n因为如果你有一个合数 t<n与 t=p*q与 p>1和q>1那么它必须是 p<sqrt(n)或q<sqrt(n)因此 t 的位置当您停在k=sqrt(n)时已经被标记了.