#include <bits/stdc++.h>
using namespace std;

int main() {
    const int n = 1e8;
    vector<bool> asal_mi(n + 1, 1);
    vector<int> asal_sayisi(n + 1);
    for (int i = 2; i <= n; i++) {
        asal_sayisi[i] = asal_sayisi[i - 1] + asal_mi[i];
        if (!asal_mi[i])
            continue;
        for (int k = 2 * i; k <= n; k += i)
            asal_mi[k] = false;
    }

    auto araliktaki_asal_sayisi = [&](int l, int r) {
        l = max(l, 1);
        return asal_sayisi[r] - asal_sayisi[l - 1];
    };

    cout << "[1, " << n << "] araligindaki asal sayisi: " << araliktaki_asal_sayisi(1, n) << "\n";

    // https://c...content-available-to-author-only...s.com/blog/entry/61587
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int ornek = 0; ornek < 5; ornek++) {
        int l = uniform_int_distribution<int>(1, n)(rng);
        int r = uniform_int_distribution<int>(l, n)(rng);
        cout << "[" << l << ", " << r << "] araligindaki asal sayisi: " << araliktaki_asal_sayisi(l, r) << "\n";
    }
}