SPOJ Prime Intervals

// Accepted
// Time: 0.74

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

#define sf scanf
#define pf printf
#define DIFF 1000010
#define limit 46400
#define l_limit 216
#define mset(c,v) memset(c , v , sizeof(c))

typedef long long LL;

LL prm[DIFF], plen=0;

bool mark[DIFF], primenow[DIFF];

void sieve(LL n)
{
    LL i,j;

    mset(mark, true);

    for(i=2; i*i<limit; i++)
    {
        if(mark[i])
        {
            for(j=i*i; j<limit; j+=i)
            {
                mark[j] = false;
            }
        }
    }

    for(i=2; i<limit; i++)
    {
        if(mark[i])
        {
            prm[plen++] = i;
        }
    }
}

int main()
{
    int t;
    sf("%d", &t);
    while(t--)
    {
        plen=0;
        LL L, U , i, j , p , s;
        sf("%lld %lld", &L, &U);

        sieve(U);

        mset(primenow, true);

        for(i=0; i<plen; i++)
        {
            p = prm[i];
            s = L / p;
            s*=p;

            for(j=s; j<=U; j+=p)
            {
                if(j < L) continue;

                primenow[j-L] = false;
            }
        }

        for(i=0; i<plen; i++)
        {
            if(prm[i]>=L and prm[i]<=U)
            {
                pf("%lld\n",prm[i]);
            }
        }

        for(i=0; i<U-L+1; i++)
        {
            if(primenow[i]==true and (i+L)!=1)
            {
                pf("%lld\n", i+L);
            }
        }
    }

    return 0;
}