Cod sursa(job #1010601)
Utilizator | Data | 15 octombrie 2013 12:38:40 | |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include <stdio.h>
#include <stdlib.h>
const int nmax = int(2e6) + 2;
char p[nmax];
int sieve(int n) {
int ret = 1;
for(int i = 3;i*i <= n;i += 2) {
if(p[i] == 0) {
for(int j = i + i + i;j <= n;j += i*2) {
p[j] = 1;
}
}
}
for(int i = 3;i <= n;i += 2) {
ret += p[i] ^ 1;
}
return ret;
}
int main()
{
freopen("ciur.in","r",stdin);
freopen("ciur.out","w",stdout);
int n;
scanf("%d",&n);
printf("%d\n",sieve(n));
return 0;
}