1.我发现不管是时间复杂度还是空间复杂度,第二段程序都优于第一段程序。所以,这道题目应该用单数组做(纯粹按照筛选求质数的思路做),这样做更好一些(而且还更加简单易懂).
2程序都在这
第一段程序:
#include<bits/stdc++.h>
//#define maxn 5000005
using namespace std;
const int maxn=5000005;
int a[maxn],b[maxn],s,e,t,ans=0;
int main()
{
cin>>s>>e;
for(int i=2;i<=e;i++)//1不是素数
{
if(!a[i]) b[t++]=a[i]=i;
for(int j=0;j<t&&i*b[j]<=e;j++)
{
a[i*b[j]]=b[j];
if(a[i]==b[j]) break;
}
}
for(int i=s;i<=e;i++) ans+=(a[i/a[i]]==i/a[i]);
cout<<ans;
return 0;
}
第二段程序:
#include<bits/stdc++.h>
//#define maxn 5000005
using namespace std;
const int maxn=5000005;
int a[maxn],s,e,ans=0;
int main()
{
cin>>s>>e;
for(int i=2;i<=e;i++)//1不是素数
{
if(a[i]==0) a[i]=i;
for(int j=2;j<=e/i;j++)
if(a[i*j]==0) a[i*j]=i;
}
for(int i=s;i<=e;i++)
{
int x=i/a[i];
if(x==a[x]) ans++;
}
cout<<ans;
return 0;
}
最后
以上就是贪玩宝马最近收集整理的关于2014常州市“信息与未来”程序设计小能手比赛试题--半质数补充的全部内容,更多相关2014常州市“信息与未来”程序设计小能手比赛试题--半质数补充内容请搜索靠谱客的其他文章。
发表评论 取消回复