UVa 10539 - Almost Prime Numbers(筛选求素数)

给出两个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博客 ,格式可能有所偏差。

支付宝扫码领红包