UVA 10539 - Almost Prime Numbers

题意：给定一个区间，求这个区间中的Almost prime number，Almost prime number的定义为：仅仅能整除一个素数。

思路：既然是仅仅能整除一个素数，那么这些数肯定为素数的x次方（x > 1)，那么仅仅要先打出素数表，然后在素数表上暴力找一遍就能够了，由于素数表仅仅要找到sqrt(Max),大概100W，然后每一个数找的复杂度为log(n),这样复杂度是能够接受的。

代码：

#include 
     
      #include 
      
       const int N = 1000005;int t, vis[N], pn = 0;long long l, r, prime[N];int main() {	for (int i = 2; i < N; i++) {		if (vis[i]) continue;		prime[pn++] = i;		for (int j = i; j < N; j += i)			vis[j] = 1; 	}	scanf("%d", &t);	while (t--) {		scanf("%lld%lld", &l, &r);		long long ans = 0;		for (int i = 0; i < pn; i++) {			for (long long j = prime[i] * prime[i]; j <= r; j *= prime[i]) {				if (j >= l) ans++;   			}  		}  		printf("%lld\n", ans); 	}	return 0;}