几乎是素数 Almost Prime Numbers

题面翻译

输入两个正整数 L , U ( L ≤ U < 1 0 12 ) L,U(L\leq U<10^{12}) L,U(L≤U<1012),统计区间$[L,U]$的整数中有几个满足：它本身不是素数，但只有一个素因子。例如，$4$、$27$都满足条件。

Translated by @HNFMS_tomoo @Planet6174

题目描述

PDF

[外链图片转存中…(img-3x1cJOkQ-1661664780185)]

输入格式

[外链图片转存中…(img-oN463RZD-1661664780187)]

输出格式

[外链图片转存中…(img-hXhpfC9B-1661664780188)]

样例 #1

样例输入 #1

3
1 10
1 20
1 5

样例输出 #1

3
4
1

很简单，直接上代码！

代码

#includeusing namespace std;int cnt,n,T;long long a[2000000],l,r,b[2000000];void aa(int n)
{for(int i=2;i<=n;i++) {if(!a[i]) {b[cnt++] = i;}for(int j=0;j<cnt&&b[j]*i<n;j++) {a[i*b[j]]=1;if(i%b[j]==0){break;}}}	
}int main() 
{aa(1000005);cin>>T;while(T--) {cin>>l>>r;long long ans=0;for(int i=0;i<cnt;i++){for(long long j=b[i]*b[i];j<=r;j*=b[i]){if(j>=l) {ans++;}} }cout<<ans<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！