这是埃拉托色尼筛法的什么变体？

Question

我正在尝试解决一个问题 Prime Path on spoj, and I am trying to understand the solution I found on github. The broad logic to solve this problem is to generate all four digit primes and add an edge iff we can go from one prime to the next by changing a single digit. This solution I found uses sieve to generate all primes. The sieve of eratosthenes wiki 上的问题与此解决方案中的筛选功能不同。只需要帮助理解以下代码中筛功能的变化：

#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

I am unable to understand why the author has listed only the odd numbers to calculate the primes

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

and why the loops run upto LMT, i.e 100?

因为100 * 100 = 10000，所以你可以通过筛到100来筛选所有4位素数。通过标记数字的倍数<= 100，你也会处理数字x > 100 是非素数，因此必须有低于 sqrt(x).

的除数

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

请注意 i << 1 就是 2*i。为什么 2*i？请记住，我们只关心奇数。 i*i + i = i*(i+1)，这将是偶数，依此类推，如果您使用 + i，有时您会遇到偶数。所以代码使用 + 2i 来避免落在偶数上。

此外，我们从 i*i 开始，因为之前的数字将被 i 的先前迭代筛选，出于同样的原因：如果 j < i*i 不是素数，它最多必须有一个因子 sqrt(j)，这在之前已经被解决了。

如果你愿意，你可以进一步优化代码，如练习：

你只筛选了奇数，但你仍然为偶数分配内存。用一半内存实现筛子；
每个数字只需要 1 位。使用更少 16 倍的内存实现筛子（不为每个数字使用 bool 减少 8 倍，不为偶数分配内存减少 2 倍）。

这是埃拉托色尼筛法的什么变体？

What variation of Sieve of Eratosthenes is this?

c++

algorithm

primes

sieve-of-eratosthenes