UVA-10539 Almost Prime Numbers

题目大意：这道题中给了一种数的定义，让求在某个区间内的这种数的个数。这种数的定义是：有且只有一个素因子的合数。

题目分析：这种数的实质是素数的至少两次幂。由此打表——打出最大区间里的所有这种数构成的表即可。

代码如下：

 # include<iostream>

 # include<cstdio>

 # include<cmath>

 # include<set>

 # include<cstring>

 # include<algorithm>

 using namespace std;

 const long long N=;

 # define ll long long

 int pri[],mark[];

 set<ll>s;

 ll mypow(int a,int b)

 {

     if(b==)

         return a;

     ll u=mypow(a,b/);

     u*=u;

     if(b&)

         u*=a;

     return u;

 }

 void init()

 {

     pri[]=;

     memset(mark,,sizeof(mark));

     for(int i=;i<=;++i){

         if(!mark[i])

             pri[++pri[]]=i;

         for(int j=;j<=pri[]&&i*pri[j]<=;++j){

             mark[i*pri[j]]=;

             if(i%pri[j]==)

                 break;

         }

     }

     for(int i=;i<=pri[];++i){

         ll u=(pri[i]+0LL)*(pri[i]+0LL);///在这要对pri[i]进行强制类型转换，否则溢出。

         while(u<N){

             s.insert(u);

             u=u*pri[i];

         }

     }

 }

 void work(ll a,ll b)

 {

     int ans=;

     set<ll>::iterator it1,it2;

     it1=lower_bound(s.begin(),s.end(),a);

     it2=lower_bound(s.begin(),s.end(),b);

     while(it1!=it2){

         ++it1;

         ++ans;

     }

     printf("%d\n",ans);

 }

 int main()

 {

     init();

     int T;

     ll l,r;

     scanf("%d\n",&T);

     while(T--)

     {

         scanf("%lld%lld",&l,&r);

         work(l,r);

     }

     return ;

 }

对于这一类问题：一定要理解透彻题中的新定义，否则费了半天劲写出来的东西是错的，既浪费时间，又浪费精力。