uva 10539 - Almost Prime Numbers(數論)

題目鏈接：uva 10539 - Almost Prime Numbers

題目大意：給出范圍low~high,問說在這個范圍內有多少個數滿足n=pb,(p為素數).

解題思路：首先處理出1e6以內的素數，然後對於每個范圍，用solve(high)?solve(low?1),solve(n)用來處理小於n的滿足要求的數的個數。枚舉素數，判斷即可。

#include 
#include 

typedef long long ll;

const int maxn = 1e6;
ll lower, up, prime[maxn];
int cp, v[maxn];

void primeTable (int n) {

    cp = 0;
    memset(v, 0, sizeof(v));

    for (int i = 2; i <= n; i++) {
        if (v[i])
            continue;

        prime[cp++] = i;
        for (int j = 2 * i; j <= n; j += i)
            v[j] = 1;
    }
}

ll solve (ll n) {
    ll ans = 0;

    for (int i = 0; i < cp; i++) {
        ll u = prime[i] * prime[i];

        if (u > n)
            break;

        while (u <= n) {
            u *= prime[i];
            ans++;
        }
    }
    return ans;
}

int main () {
    primeTable(maxn);
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%lld%lld", &lower, &up);
        printf("%lld\n", solve(up) - solve(lower-1));
    }
    return 0;
}