What variation of Sieve of Eratosthenes is this?

Question

I am trying to solve a problem 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 on wiki is different compared to the sieve function in this solution. Just need help on understanding the variation of sieve function in the following code:

#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;
}

What is the sieve function computing here? I am unable to understand why the author has listed only the odd numbers to calculate the primes, and why the loops run upto LMT, i.e 100? Appreciate your help.

@πάντα ῥεῖ Well, the smallest even number is prime ;-) — Sergey Kalinichenko
@dasblinkenlight Well, true that. Anyway that's easy to test for ;-) ... — πάντα ῥεῖ

IVlad IVlad · Accepted Answer · 2015-07-26T13:38:06

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

Because the only even prime is 2, the rest are all odd. So you only need to check odd numbers.

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

Because 100 * 100 = 10000, so you can sieve all 4 digit primes by doing the sieve up to 100. By marking off multiples of numbers <= 100, you will also take care of numbers x > 100 that are non-prime and therefore must have divisors below sqrt(x).

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

Note that i << 1 is just 2*i. Why 2*i? Remember that we only care about the odd numbers. i*i + i = i*(i+1), which will be even, and so on, you will land on even numbers sometimes if you use + i. So the code uses + 2i to avoid landing on even numbers.

Also, we start from i*i because the previous numbers will have been been sieved by previous iterations of i, for the same reason: if a j < i*i was not prime, it must have had a factor at most sqrt(j), which would have been addressed previously.

You can optimize the code even more if you want, as exercises:

You only sieve the odd numbers, but you still alocate memory for the evens. Implement the sieve with half the memory;
You only need 1 bit for each number. Implement the sieve with 16 times less memory (8 times less for not using a bool for each number and 2 times less for not allocating memory for the even numbers).

What variation of Sieve of Eratosthenes is this?

1 Answers