题目链接：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; }