这是埃拉托斯特尼筛的什么变体？

Question

我正在尝试解决spoj上的Prime Path问题，我正在尝试理解在github上找到的解决方案。解决这个问题的广义逻辑是生成所有四位数素数，并添加一个边，如果我们可以通过更改一个数字从一个素数转到下一个素值。我找到的这个解决方案使用筛子来生成所有素数。与此解决方案中的筛分功能相比，维基上的稀土筛分功能有所不同。只需要帮助了解以下代码中筛分函数的变化：

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 10000
#define LMT 100

bool flag[MAX], visited[MAX];
int d[MAX];

void sieve()
{
    register int i, j, k;
    flag[0] = flag[1] = 1;
    for(i=1000; i<MAX; i+=2) 
        flag[i] = 1;
    for(i=3; i<LMT; i+=2)
        if(!flag[i])
            for(j=i*i, k=i<<1; j<MAX; j+=k)
                flag[j] = 1;
}

int bfs(int start, int end)
{
    queue< int > Q;
    int i, u, v, t, j;
    char temp[10], x;
    Q.push(start);
    memset(visited, 0, sizeof visited);
    memset(d, -1, sizeof d);
    d[start] = 0;
    visited[start] = 1;
    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        sprintf(temp,"%d",u);
        x = temp[0];
        for(t=0;t<4;t++)
        {
            if(t==0 || t==3) 
                i=1; 
            else
                i=0;
            if(t==3) 
                j=2;
            else
                j=1;
            x = temp[t];
            for(;i<=9;i+=j)
            {
                temp[t] = i+'0';
                v = atoi(temp);
                if(v!=u && !visited[v] && !flag[v])
                {
                    Q.push(v);
                    visited[v] = 1;
                    d[v] = d[u]+1;
                    if(v==end) 
                        return d[end];
                }
            }
            temp[t] = x;
        }
    }
    return d[end];
}

int main()
{
    int a, b, t, dist;
    sieve();
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &a, &b);
        if(a==b) 
        {
            printf("0\n"); 
            continue; 
        }
        dist = bfs(a,b);
        if(dist==-1) 
            printf("impossible\n");
        else 
            printf("%d\n", dist);
    }
    return 0;
}

这里的筛选函数计算是什么？我无法理解为什么作者只列出奇数来计算素数，为什么循环达到LMT，即100？感谢你的帮助。

Answer 1

我不明白为什么作者只列出了奇数来计算质数

因为唯一的偶素数是2，其余的都是奇数。所以你只需要检查奇数。

为什么循环运行到LMT，即100？

因为< code>100 * 100 = 10000，所以您可以通过筛选到100来筛选所有4位素数。通过标出数字的倍数<代码>

for(j=i*i, k=i<<1; j<MAX; j+=k)
    flag[j] = 1;

注意i

此外，我们从i*i开始，因为之前的数字将被i的先前迭代筛选，原因相同：如果j

如果需要，您可以进一步优化代码，作为练习：

>

你只筛选奇数，但你仍然为偶数分配内存。用一半的内存实现筛子;

每个数字只需要 1 位。实现内存减少 16 倍的筛网（对于每个数字不使用 bool，减少 8 倍，对于不为偶数分配内存，则少 2 倍）。