【题解】还不是质数

题意

求区间内，其本身不是质数但是只有一个质因子的数有多少个。

题解

首先确定这样的数是什么，是质数的次幂形式，因为只有这样的数他本身不是质数但是其质因子只有一个。那么我们看数据范围，符合条件的数至少是质数的平方，所以我们只用找之内的质数就好了。对于每个找到的质数，我们将其小于的次幂都存在一个数组当中。由于次幂增长的很快，所以这样的数的个数大概只有个。然后我们把存下的数进行排序。然后对于给定的区间，我们用二分去找上下界，一减就是区间范围内这样数的个数了。注意的是若用c++，上界可以用，下界用去找。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int prime[N];
int vis[N];
int cnt=0;
int tot=0;
long long num[N];
void init()
{
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            for(long long j=i*i;j<=1e12;j=j*i)
            {
                num[tot++]=j;
            }
        }
        for(int j=0;j<N&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    sort(num,num+tot);
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long l,r;
        scanf("%lld%lld",&l,&r);
        printf("%d\n",upper_bound(num,num+tot,r)-lower_bound(num,num+tot,l));
    }
    return 0;
}