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:
47
Sample Output 1:
Yes
41
Sample Input 2:
21
Sample Output 2:
No
23 标题大意：性感素数是指形如 (p, p+6) 这样的一对素数。给定一个整数，判定其是否为一个性感素数。若N是一个性感素数，则在一行中输出Yes，并在第二行输出与N配对的另一个性感素数（若配对的数不唯一，输出较小的谁人）。若N不是性感素数，则在一行中输出No，然后在第二行输出大于N的最小性感素数。
分析：分别判定p和p-6，p和p+6是否同时为素数，假如是，则为性感素数输出Yes。不是的话就从p+1往后找到第一个满足要求的数。
#include<algorithm>
#include <iostream>
#include<cstdlib>
#include<cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;
int num={1,1},prime;
int getprime()
{
int t=0;
for(int i=2;i<=1000;++i)
if(num==0)
for(int j=i*i;j<=1000000;j+=i)
num=1;
for(int i=2;i<=1000000;++i)
if(num==0)prime=i;
return t;
}
bool judge(int a,int t)
{
if(a==1)return 0;
for(int i=0;i<t;++i)
if(a%prime==0&&a!=prime)return 0;
return 1;
}
void getans(int n,int t)
{
while(n)
{
if(judge(n,t)==1)
{
if(judge(n-6,t)==1)
{
printf("No\n%d\n",n);
return;
}
else if(judge(n+6,t)==1)
{
printf("No\n%d\n",n);
return;
}
}
n++;
}
return;
}
int main(void)
{
#ifdef test
freopen("in.txt","r",stdin);
//freopen("in.txt","w",stdout);
clock_t start=clock();
#endif //test
int cnt=getprime();
int n,ans=0;scanf("%d",&n);
bool f=judge(n,cnt),f1;
if(f)
{
f1=judge(n-6,cnt);
if(!f1)
{
f1=judge(n+6,cnt);
if(f1)printf("Yes\n%d\n",n+6);
else getans(n+1,cnt);
}
else printf("Yes\n%d\n",n-6);
}
else getans(n+1,cnt);
#ifdef test
clockid_t end=clock();
double endtime=(double)(end-start)/CLOCKS_PER_SEC;
printf("\n\n\n\n\n");
cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位
cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位
#endif //test
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]