Cod sursa(job #2586826)

Utilizator sulzandreiandrei sulzandrei Data 21 martie 2020 16:54:27
Problema Ciurul lui Eratosthenes Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

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

#define ull long long int
ull gcd(ull a, ull b){ return (b==0)?a:gcd(b,a%b);}

bool isPrime(ull n){

    for(int i = 2; i*i <= n; i++){
        if (gcd(n,i) != 1){
            return false;
        }
    }

    return true;
}

int main ( )
{
   ull n,primes=0;
   in>>n;

   for(int i = 2;  i<=n;i++){
        if (isPrime(i)){
            primes++;
        }

   }
    out<<primes;

    return 0;
}