#include<iostream> #include<cstdio> #include<cmath> #include<string> using namespace std; typedef long long ll; const int maxn=1000001; int prime[maxn],p[maxn],cnt; bool res[maxn]; void findPrime(int m) //使用埃式素数筛法 { for(int i=2;i<=m;i++) { if(p[i]==false) prime[++cnt]=i; for(int j=i+i;j<=m;j+=i) p[j]=true; } } int main(void) { int n,m; cin>>n>>m; findPrime((int)sqrt(m)); for(int i=1;i<=cnt;i++)//对cnt个包含 所有的 可能是区间[n,m]中 合数因子 的集合 进行枚举 { //cout<<prime[i]<<endl; for(ll j=(n+prime[i]-1)/prime[i]*prime[i];j<=m;j+=prime[i])//把[n,m]中是素数表中素数至少为2倍的数标记 { //j是区间[n,m]中第一个是素数prime[i]整数倍数的数值 if(j==prime[i]) continue; else res[j-n]=true; } } int count=0; for(int i=0;i<=m-n;i++) if(res[i]==false) count++; cout<<count; return 0; }
解题思路:
注意事项:
参考代码:
0.0分
2 人评分
求组合数 (C语言代码)浏览:1153 |
WU-printf基础练习2 (C++代码)浏览:2000 |
WU-C语言程序设计教程(第三版)课后习题11.12 (C++代码)(想学链表的小伙伴可以看看)浏览:898 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:535 |
三角形 (C语言代码)浏览:903 |
简单的a+b (C语言代码)浏览:524 |
Hello, world! (C语言代码)浏览:824 |
C语言程序设计教程(第三版)课后习题10.7 (用指针求解)浏览:1460 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:1028 |
【计算两点间的距离】 (C语言代码)浏览:844 |