Cod sursa(job #349361)
Utilizator | Teodor Plop Teodor94 | Data | 19 septembrie 2009 11:10:50 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.43 kb |
#include <cstdio>
const int N = (1<<21);
bool c[N];
int main()
{
freopen("ciur.in","r",stdin);
freopen("ciur.out","w",stdout);
int n,j,i,nr;
scanf("%d",&n);
for (i=2;i*i<=n;++i)
if (!c[i]) // (!c[i]) = (c[i]==0) = (c[i]!=1) daca este prim
for (j=i*i; j<=n; j+=i) // j+=i = j=j+i
c[j]=true;
nr=0;
for (i=2;i<=n;i++)
if (!c[i]) nr++;
printf("%d",nr);
return 0;
}