Cod sursa(job #2524566)

Utilizator RaresCosaAndrei-Rares Cosa RaresCosa Data 15 ianuarie 2020 21:16:29
Problema Ciurul lui Eratosthenes Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
using namespace std;

ifstream fin("ciur.in");
ofstream fout("ciur.out");

int numar_div(int x) {
    int exp = 0;
    while (x % 2 == 0) {
        ++exp;
        x /= 2;
    }
    int nrd = exp + 1;
    int d = 3;
    while (d * d <= x) {
        exp = 0;
        while (x % d == 0) {
            ++exp;
            x /= d;
        }
        nrd *= (exp + 1);
        d += 2;
    }
    if (x != 1)
        nrd *= 2;
    return nrd;
}

int main() {
    int n;
    fin >> n;
    int nr_prime = 0;
    for (int i = 2; i <= n; ++i) {
        int nrdiv = numar_div(i);
        if (nrdiv == 2)
            ++nr_prime;
    }
    fout << nr_prime;
}