UVa 10539 - Almost Prime Numbers（筛选求素数）

发表于 分类于 ， Disqus：

给出两个1e12以内的数，求有多少不是素数，但是一个素数的n次方（n>1）数。

一开始用set存了所有的数，之后用set.find()循环求得两个迭代器，再用distance求个数，但是因为所求的数的间隔较大，循环会超时……虽然超时了， 但是学了求迭代器距离的方法，收获也挺大。

后来改为如下做法，首先打素数表，然后分别求比所给的两个数小的数的个数，求两者差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000010;
LL isp[78500],pre_p;
bool np[maxn]={true,true};
void prime(){
    for(int i=2;i<maxn;++i){
        if(!np[i])
            isp[pre_p++]=i;
        for(int j=0;j<pre_p&&i*isp[j]<maxn;++j){
            np[i*isp[j]]=true;
            if(!(i%isp[j])) break;
        }
    }
    return;
}
LL solve(LL n){
    LL cnt=0;
    for(int i=0;i<pre_p;++i){
        LL cur=isp[i]*isp[i];
        while(cur<n) cur*=isp[i],++cnt;
    }
    return cnt;
}
int main(){
    prime();
    int t;
    scanf("%d",&t);
    while(t--){
        LL l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",solve(r+1)-solve(l));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章