Cod sursa(job #948108)
Utilizator | Data | 9 mai 2013 15:00:15 | |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXSIZE 2000000/2+1
char p[MAXSIZE];
int Primes_4(int n)
{
int i, j, nr = 1;
for (i = 1; 2*(2*i*i+2*i)+1 <= n; i ++)
if (p[i] == 0)
for (j = 2*i*i+2*i; 2*j+1 <= n; j += 2*i+1)
p[j] = 1;
for (i=1; 2*i+1 <= n; ++i)
if (p[i] == 0) nr++;
return nr;
}
int main()
{
freopen("ciur.in", "r", stdin);
freopen("ciur.out", "w", stdout);
int N;
cin >> N;
cout << Primes_4(N) << '\n';
return 0;
}