Cod sursa(job #2664621)
Utilizator | Data | 29 octombrie 2020 00:03:55 | |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <cstdio>
using namespace std;
const int NMAX = 2000000;
const int base = 32;
int ciur[(NMAX >> 6) + 5];
int main()
{
freopen("ciur.in", "r", stdin);
freopen("ciur.out", "w", stdout);
int n, nr, i, j;
nr = 1;
scanf("%d", &n);
for(i = 3 ; i * i <= n ; i += 2)
if( !(ciur[i / (2 * base)] & (1 << (i % base))) )
{
for(j = i * i ; j <= n ; j += (i << 1))
ciur[j / (2 * base)] |= (1 << (j % base));
nr ++;
}
printf("%d\n", nr);
return 0;
}