Submission #3774837

---

Source Code Expand

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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

const int MAX_N=1e6;

bool is_prime_small[MAX_N+1];
int cnt[MAX_N+1];
int num[MAX_N+1];

int segment_sieve(int a, int b){
    for(ll i=2; i*i<b; ++i){
        is_prime_small[i] = true;
    }
    rep(i, b-a){
        num[i] = i+a;
    }
    for(int i=2; i*i<b; ++i){
        if(is_prime_small[i]){
            for(ll j=2*i; j*j<b; j+=i) {
                is_prime_small[j] = false;
            }
            ll tmp=i;
            while(tmp < b){
                for(ll j = max((ll)2, (a+tmp-1)/tmp)*tmp; j<b; j+=tmp){
                    ++cnt[j-a];
                    num[j-a]/=i;
                }
                tmp*=i;
            }
        }
    }
    int res=0;
    rep(i, b-a){
        if(num[i]!=1){
            ++cnt[i];
        }
        if(is_prime_small[cnt[i]]){
            ++res;
        }
    }
    return res;
}

int main(){
    int l, r;
    cin >> l >> r;
    cout << segment_sieve(l, r+1) << nl;
    return 0;
}

Submission Info

Judge Result