Cod sursa(job #217994)
Utilizator | Alexandru-Iancu Caragicu Bit_Master | Data | 31 octombrie 2008 13:09:20 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.39 kb |
#include <stdio.h>
#include <math.h>
const int N=2000001;
bool prim [N];
int i,k,n;
int main()
{
for (i=2;i<=N;i++)
prim [i] = 1;
freopen("ciur.in","r",stdin);
freopen("ciur.out","w",stdout);
scanf("%d",&n);
for (i=2;i<=sqrt(n);i++)
if(prim[i])
for (k=i*i;k<=n;k=k+i)
prim [k] = 0;
k = 0;
for (i=2;i<=n;i++)
if (prim [i])
k++;
printf("%d",k);
return 0;
}