2014常州市“信息与未来”程序设计小能手比赛试题--半质数补充

75 阅读 0 评论 50 点赞

我是靠谱客的博主贪玩宝马，这篇文章主要介绍2014常州市“信息与未来”程序设计小能手比赛试题--半质数补充，现在分享给大家，希望可以做个参考。

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;
}