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

vector<int> asal_listesi(int n) {
    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;
    }
    return asallar;
}

vector<pair<long long, int>> carpanlara_ayir(long long n, const vector<int> &asallar) {
    vector<pair<long long, int>> asal_carpan_kuvvetleri;
    for (long long bolen : asallar) {
        if (bolen * bolen > n)
            break;
        if (n % bolen)
            continue;
        int us = 0; // Asal üssü
        while (n % bolen == 0) {
            n /= bolen;
            us++;
        }
        asal_carpan_kuvvetleri.push_back({bolen, us});
    }
    if (n > 1) {
        asal_carpan_kuvvetleri.push_back({n, 1});
    }
    return asal_carpan_kuvvetleri;
}

int main() {
    const int n = 1e8;
    auto asallar = asal_listesi(n);
    const int sorgu_sayisi = 4e6;
    int toplam_asal_carpan_sayisi = 0; // Derleyici optimizasyonlarının önüne geçmek için.
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int ornek = 0; ornek < sorgu_sayisi; ornek++) {
        int sayi = uniform_int_distribution<int>(1, n)(rng);
        auto asal_carpan_kuvvetleri = carpanlara_ayir(sayi, asallar);
        for (auto &[asal, us] : asal_carpan_kuvvetleri)
            toplam_asal_carpan_sayisi += us;
    }
    cout << toplam_asal_carpan_sayisi << "\n";
}