ACM_数数？诶？这么简单？

Problem Description:

当看到GDUFE-GAME宣传海报上提到"场内人员可以在任意区域组织游戏"时，QWER按不住自己蠢蠢欲动的心，当场就出了一道题：定义QWER数为任意相邻两个素数之和加上1且是素数的数(eg: 6 = 2 + 3 + 1, 6不是素数, 所以6不是QWER数; 13 = 5 + 7 + 1, 13是素数，所以13是QWER数)，给出一个数字n，10秒内求出1到n之间所有QWER数便能获得QWER的一次拥抱。作为QWER的迷弟/迷妹，你也按不住自己放在键盘上的麒麟臂，飞速得写代码，准备去收下QWER的拥抱。

Input:

数据包括多个测试实例。

每个测试实例包含一个整数 n (15 ≤ n ≤ 1000000)。

Output:

对于每个测试实例，从小到大输出 1 到 n 之间所有的QWER数(每个QWER数之间间隔一个空格)。

Sample Input:

15

20

Sample Output:

13

13 19
解题思路：先用线性筛打素数表，接下来给定范围内枚举相邻的素数和加1是否满足是素数且不超过n则保存在qwer数组中，最后输出。要用线性筛啊，不然老TLE！！！

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXSIZE 1000000

 bool isp[MAXSIZE];

 int prime[MAXSIZE],qwer[MAXSIZE];//保存素数

 int main()

 {

     int cnt=;

     memset(isp,true,sizeof(isp));  //打素数表

     memset(prime,,sizeof(prime));

     isp[]=isp[]=false;

     for(int i=;i<MAXSIZE;++i){

         if(isp[i])

             prime[++cnt]=i;//从下标1开始保存素数

         for(int j=;j<=cnt && i*prime[j]<MAXSIZE;++j){

             isp[i*prime[j]]=false;

             if(i%prime[j]==)

                 break;

         }

     }

     int tmp,k,n;

     while(cin>>n){

         tmp=k=;

         for(int i=;prime[i]<=n;++i){  //从2开始枚举

             tmp=prime[i-]+prime[i]+;

             if(tmp>n)break;

             if(isp[tmp])qwer[++k]=tmp;

         }

         for(int i=;i<k;++i)

             cout<<qwer[i]<<' ';

         cout<<qwer[k]<<endl;

     }

     return ;

 }

巴特西

ACM_数数？诶？这么简单？

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章