Submission #1794378

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
vector<int> makePrimes(int n) {
    vector<int> res, primes(n + 1, 1);
    primes[0] = primes[1] = 0;
    rep(i, 2, sqrt(n)) if (primes[i]) for (int j = 0; i * (j + 2) < n; j++) primes[i * (j + 2)] = 0;
    rep(i, 2, n + 1) if (primes[i]) res.push_back(i);
    return res;
}
bool isprime(int v) {
    if (v == 1) return false;
    for (int i = 2; 1LL * i*i <= v; i++) if (v%i == 0) return false;
    return true;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



int L, R;
int A[1010101];
int cnt[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L >> R;

    vector<int> primes = makePrimes(40101);

    rep(i, L, R + 1) A[i - L] = i;
    fore(p, primes) {
        for (int l = (L + p - 1) / p * p; l <= R; l += p) {
            while (A[l - L] % p == 0) A[l - L] /= p, cnt[l - L]++;
        }
    }

    rep(i, 0, R - L + 1) if (1 < A[i]) cnt[i]++;
    int ans = 0;
    rep(i, 0, R - L + 1) {
        if (isprime(cnt[i]) and 0 < cnt[i]) ans++;
    }
    cout << ans << endl;
}

Submission Info

Judge Result