Submission #3873345

---

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];
ll n[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){
        n[i]=i+l;
    }
    rep(j,1,c+1){
        ll i=(l+prime[j]-1)/prime[j]*prime[j];
        while(i<=r){
            while(n[i-l]%prime[j]==0){
                d[i-l]++;
                n[i-l]/=prime[j];
            }
            i+=prime[j];
        }
    }
    rep(i,0,r-l+1){
        if(n[i]!=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