Cod sursa(job #2229064)
Utilizator | Anders inquisitor | Data | 5 august 2018 19:55:19 |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.06 kb |
#include <stdio.h>
int p[2000000];
int sieve(int n)
{
int i, j, nr = (n > 1) + (n > 2);
for(i = 5; i * i <= n; i += 4)
{
if(p[i] == 0)
{
for(j = 5 * i; j <= n; j += 4 * i)
{
p[j] = 1;
if((j += 2 * i) <= n) p[j] = 1;
}
}
i += 2;
if(i * i <= n)
{
if(p[i] == 0)
{
for(j = 5 * i; j <= n; j += 4 * i)
{
p[j] = 1;
if((j += 2 * i) <= n) p[j] = 1;
}
}
}
}
for(i = 5; i <= n; i += 4)
{
if(p[i] == 0)
{
++nr;
}
if((i += 2) <= n)
{
if(p[i] == 0)
{
++nr;
}
}
}
return nr;
}
int main()
{
freopen("ciur.in", "r", stdin);
freopen("ciur.out", "w", stdout);
int N; scanf("%d", &N);
printf("%d ", sieve(N));
return 0;
}