1156 Sexy Primes (20)

Sexy primes are pairs of primes of the form (p, p+6), so-named since "sex" is the Latin word for "six". (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)
Now given an integer, you are supposed to tell if it is a sexy prime.
Input Specification:

Each input file contains one test case. Each case gives a positive integer N (≤10^8).
Output Specification:

For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.
Sample Input 1:

1. 47

复制代码

Sample Output 1:

1. Yes
2. 41

复制代码

Sample Input 2:

1. 21

复制代码

Sample Output 2:

1. No
2. 23

复制代码

 标题大意：性感素数是指形如 (p, p+6) 这样的一对素数。给定一个整数，判定其是否为一个性感素数。若N是一个性感素数，则在一行中输出Yes，并在第二行输出与N配对的另一个性感素数（若配对的数不唯一，输出较小的谁人）。若N不是性感素数，则在一行中输出No，然后在第二行输出大于N的最小性感素数。
分析：分别判定p和p-6，p和p+6是否同时为素数，假如是，则为性感素数输出Yes。不是的话就从p+1往后找到第一个满足要求的数。

1. #include<algorithm>
2. #include <iostream>
3. #include  <cstdlib>
4. #include  <cstring>
5. #include   <string>
6. #include   <vector>
7. #include   <cstdio>
8. #include    <queue>
9. #include    <stack>
10. #include    <ctime>
11. #include    <cmath>
12. #include      <map>
13. #include      <set>
14. #define INF 0xffffffff
15. #define db1(x) cout<<#x<<"="<<(x)<<endl
16. #define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
17. #define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
18. #define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
19. #define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
20. using namespace std;
22. int num[1000005]={1,1},prime[100000];
23. int getprime()
24. {
25.     int t=0;
26.     for(int i=2;i<=1000;++i)
27.         if(num[i]==0)
28.             for(int j=i*i;j<=1000000;j+=i)
29.                 num[j]=1;
30.     for(int i=2;i<=1000000;++i)
31.         if(num[i]==0)prime[t++]=i;
33.     return t;
34. }
36. bool judge(int a,int t)
37. {
38.     if(a==1)return 0;
39.     for(int i=0;i<t;++i)
40.         if(a%prime[i]==0&&a!=prime[i])return 0;
41.     return 1;
42. }
44. void getans(int n,int t)
45. {
46.     while(n)
47.     {
48.         if(judge(n,t)==1)
49.         {
51.             if(judge(n-6,t)==1)
52.             {
53.                 printf("No\n%d\n",n);
54.                 return;
55.             }
56.             else if(judge(n+6,t)==1)
57.             {
58.                 printf("No\n%d\n",n);
59.                 return;
60.             }
61.         }
62.         n++;
63.     }
64.     return;
65. }
67. int main(void)
68. {
69.     #ifdef test
70.     freopen("in.txt","r",stdin);
71.     //freopen("in.txt","w",stdout);
72.     clock_t start=clock();
73.     #endif //test
75.     int cnt=getprime();
76.     int n,ans=0;scanf("%d",&n);
78.     bool f=judge(n,cnt),f1;
79.     if(f)
80.     {
81.         f1=judge(n-6,cnt);
82.         if(!f1)
83.         {
84.             f1=judge(n+6,cnt);
85.             if(f1)printf("Yes\n%d\n",n+6);
86.             else getans(n+1,cnt);
87.         }
88.         else printf("Yes\n%d\n",n-6);
90.     }
91.     else getans(n+1,cnt);
93.     #ifdef test
94.     clockid_t end=clock();
95.     double endtime=(double)(end-start)/CLOCKS_PER_SEC;
96.     printf("\n\n\n\n\n");
97.     cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
98.     cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
99.     #endif //test
100.     return 0;
101. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。