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

int main() {
    const int n = 1e8;
    vector<bool> asal_mi(n + 1, 1);
    vector<int> asallar;
    for (int i = 2; i <= n; i++) {
        if (!asal_mi[i])
            continue;
        asallar.push_back(i);
        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 upper_bound(asallar.begin(), asallar.end(), r) - lower_bound(asallar.begin(), asallar.end(), l);
    };

    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";
    }
}