Cod sursa(job #2036931)

Utilizator PetruZZatic Petru PetruZ 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;
}