根据题意，可以很容易地发现，题目所要求的数都可以用形如 $ p^x$ 的式子表示（其中 $ p $ 为质数， \(x \ge 2\)），即分解成只含同一个质因子的式子。这提示我们使用构造的思想。
因为 \(n\) 最大为 $ 10 ^ {12}$，所以最大的 \(\sqrt n\) 也不会超过 \(10^6\)。考虑使用线性筛求出 \(10^6\) 以内的质数，再依次枚举每个质数 \(p\) 的幂：\(p^2\)，\(p^3\)，⋯\(p^k\)，统计其中满足 \(L \le p^k \le U\) 的个数即可。
注意，当 \(p^k > U\) 时要结束循环。
代码如下：
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll tot,a[10000001],b[10000001];
int main()
{
for(int i=2;i<=1000000;i++)
{
if(a[i]==0) b[++tot]=i;
for(int j=1;j<=tot&&i*b[j]<=1000000;j++)
{
a[i*b[j]]=1;
if(i%b[j]==0)
break;
}
}
int T;
cin>>T;
while(T--)
{
ll l,r,ans=0;
cin>>l>>r;
for(ll i=1;i<=tot;i++)
for(ll j=b[i]*b[i];j<=r;j*=b[i])
if(j>=l)
ans++;
cout<<ans<<endl;
}
return 0;
}
\(tips\) ：建议把所有变量都开long long，避免不必要的错误答案。
标签：10,10000001,int,ll,long,质数,UVA10539 From： https://www.cnblogs.com/-lilong-/p/17976795