Pagini recente » Cod sursa (job #2750690) | Cod sursa (job #217782) | Cod sursa (job #775312) | Cod sursa (job #21694) | Cod sursa (job #1195333)
#include <cstdio>
#include <cmath>
#include <bitset>
using namespace std;
const int NMAX=2000005;
bitset<NMAX> p;
int atkin(int n)
{
int limit=ceil(sqrt(n>>2)),secventa[]={2,4},index,k1,k,i,j,i2,nr=1;
for(i=1;i<limit;++i)
{
index=0;
k1=(i*i)<<2;
j=1;
if(!(i%3))
{
while(1)
{
k=k1+j*j;
if(k>n) break;
p[k]=~p[k];
j+=*(secventa+(++index&1));
}
}
else
{
while(1)
{
k=k1+j*j;
if(k>n) break;
p[k]=~p[k];
j+=2;
}
}
}
limit=ceil(sqrt(n/3));
for(i=1;i<limit;i+=2)
{
index=1;
k1=3*i*i;
j=2;
while(1)
{
k=k1+j*j;
if(k>n) break;
p[k]=~p[k];
j+=*(secventa+(++index&1));
}
}
limit=ceil(sqrt(n));
for(i=1;i<limit;++i)
{
k1=3*i*i;
if(!(i&1)) j=1,index=0;
else j=2,index=1;
while(j<i)
{
k=k1-j*j;
if(k<n) p[k]=~p[k];
j+=*(secventa+(++index&1));
}
}
p[2]=p[3]=1;
for(i=5;i<=limit;++i)
{
if(p[i])
{
i2=i*i;
for(j=i2;j<=n;j+=i2) p[j]=0;
}
}
for(i=3;i<=n;i+=2)
{
if(p[i]) ++nr;
}
return nr;
}
int main()
{
freopen("ciur.in","r",stdin);
freopen("ciur.out","w",stdout);
int n;
scanf("%d",&n);
printf("%d\n",atkin(n));
fclose(stdin);
fclose(stdout);
return 0;
}