Cod sursa(job #2036931)
| Utilizator | Data | 11 octombrie 2017 14:16:29 | |
|---|---|---|---|
| Problema | Ciurul lui Eratosthenes | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.48 kb |
#include <fstream>
#include <cmath>
using namespace std;
ifstream cin ("ciur.in");
ofstream cout("ciur.out");
bool prim[2000002];
int n, rs, i;
int main() {
cin >> n;
int p = (int)sqrt(n);
for(i = 1; i <= p; i++)
for(int j = i; 2* i * j + i + j <= n; j++) prim[2* i * j + i + j] = 1;
i = 1;
while(2 * i + 1 <= n){
if(prim[i] == 0) rs++;
i++;
}
cout << rs + 1;
return 0;
}