Cod sursa(job #2627135)

Utilizator giotoPopescu Ioan gioto Data 9 iunie 2020 22:23:07
Problema Ciurul lui Eratosthenes Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define primes {2, 3, 5, 7}
using namespace std;

const int INF = 2e9;

int lgput(int x, int p, int MOD = INF) {
    int ans = 1, aux = x;
    for (int i = 1; i <= p ; i = i << 1) {
        if (i & p) ans = (1LL * ans * aux) % MOD;
        aux = (1LL * aux * aux) % MOD;
    }

    return ans;
}

bool fermatCheck(int n, int x, int d, int base) {
    if (lgput(base, x, n) == 1) return true ;

    for (int i = 0; i <= d ; ++i) {
        if(lgput(base, x * lgput(2, i, INF), n) == n - 1) return true ;
    }

    return false;
}

bool checkPrime(int n) {
    if (n < 2) return false;

    int x = n - 1, d = 0;
    while (x % 2 == 0) {
        x = x >> 1;
        ++d;
    }

    for (auto base : primes) {
        if (n == base) return true;
        if (!fermatCheck(n, x, d, base)) return false;
    }

    return true;
}

int main() {

//    for (int i = 1; i <= 100 ; ++i) {
//        cerr << i << " ";
//        if(checkPrime(i)) cerr << "is prime";
//        else cerr << "isn't prime";
//
//        cerr << endl;
//    }

    freopen("ciur.in", "r", stdin);
    freopen("ciur.out", "w", stdout);

    int n;
    scanf("%d", &n);

    int ans = 0;
    for (int i = 1; i <= n ; ++i)
        if (checkPrime(i)) ++ans;

    printf("%d", ans);

    return 0;
}