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

Question

我正在尝试解决问题 Prime Path在 spoj 上，我试图了解我在 github 上找到的解决方案。解决这个问题的广泛逻辑是生成所有四位素数并添加一条边当且仅当我们可以通过更改一位数从一个素数转到下一个素数。我发现的这个解决方案使用 sieve 来生成所有素数。 sieve of eratosthenes与此解决方案中的 sieve 功能相比，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. 你只筛选奇数，但你仍然为偶数分配内存。用一半的内存实现筛子；

2. 每个数字只需要 1 位。用 16 实现筛子内存减少 8 倍(不为每个数字使用 bool 值减少 8 倍，不为偶数分配内存减少 2 倍)。