Hi I found that Sieve of Atkin is much faster than Sieve of Eratosthenes anyway something don't work and I have time like 1 minute. Can you help me improve my program a bit? I am not sure what's wrong and how can I make it work faster.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
const long unsigned limit = 1000001;
bool Tb[limit]={false};
Tb[2]=Tb[3]=true;
unsigned root=sqrt(limit-1);
for(unsigned x=1;x<root;++x)
for(unsigned y=1;y<root;++y)
{
unsigned N=(4*x*x)+(y*y);
if((N<=limit)&&((N%12==1)||(N%12==5)))Tb[N]=true;
N=(3*x*x)+(y*y);
if((N<=limit)&&((N%12==7)))Tb[N]=true;
N=(3*x*x)-(y*y);
if((x>y)&&(N<=limit)&&(N%12==11))Tb[N]=true;
}
for(unsigned N=5;N<root;++N)
if(Tb[N])
{
for(unsigned n=1, k=2;n<root;++k)
{
n=N*k;
Tb[n]=false;
}
}
unsigned T;
cin>>T;
while(T--)
{
unsigned n,m;
cin>>n>>m;
while(n<=m)
{
if(Tb[n])cout<<n<<endl;
++n;
}
}
cin.get();
return 0;
}