Submission #3873216

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
int prime[100000];
bool is_prime[100001];
int sieve(int n){
    int p = 0;
    rep(i,0,n+1) is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    rep(i,2,n+1){
        if (is_prime[i]){
            p++;
            prime[p]=i;
            for (int j=2*i; j<=n; j+=i) is_prime[j]=false;
        }
    }
    return p;
}
int d[1000010];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll l,r;
    cin>>l>>r;
    int c=sieve(int(sqrt(r)));
    rep(i,0,r-l+1){
        ll L=l+i;
        rep(j,1,c+1){
            while(L%prime[j]==0){
                d[i]++;
                L/=prime[j];
            }
        }
        if(L!=1) d[i]++;
    }
    ll ans=0;
    rep(i,0,r-l+1){
        if(is_prime[d[i]]) ans++;
    }
    cout<<ans<<"\n";
}

Submission Info

Judge Result