首页 > 代码库 > 素数三元组(南阳oj1156)(素数水题)

素数三元组(南阳oj1156)(素数水题)

素数三元组

时间限制:1000 ms  |  内存限制:65535 KB
难度:1
描述

    相邻三个奇数都是素数是一种非常少见的情形,也就是三个奇数p-2, p, p+2都是素数,这样就形成了一个素数三元组。请找出三个数都不超过n的所有这样的素数三元组。


输入
输入多组数据,每组测试数据为一个正整数n,n <= 5000000。
输出
输出大小不超过n的所有的素数三元组,每行按照从小到大的顺序输出一个三元组中的三个数,两个数之间用空格间隔。如果不存在这样的素数三元组,请输出“No triple”。
样例输入
1
样例输出
No triple
提示
○| ̄|_
来源
爱生活
上传者

TCM_张鹏

//素数打表超时!!!看来学新方法用来素数判定!!! 
/*#include<stdio.h>
#include<string.h>
#define N 5000010
int s[N]={1,1,0};
int main()
{
	int i,j,n,k;
	for(i=2;i*i<N;i++)
	{
		if(!s[i])
		{
			for(j=i+i;j<N;j+=i)
			s[j]=1;
		}
	}
	while(scanf("%d",&n)!=EOF)
	{
		for(i=3,k=0;i<=n-4;)
		{
			if((!s[i])&&(!s[i+2])&&(!s[i+4]))
			{
			   printf("%d %d %d\n",i,i+2,i+4);
			   k=1;
			   i+=6;
		    }
		    else
		    i+=2;
		}
		if(k==0)
		printf("No triple\n");
	}
	return 0;
}*/
//其实可以思考下,连续三个奇数都为素数的情况也就 3,5,7。 
#include<stdio.h>
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n>=7)
		printf("3 5 7\n");
		else
		printf("No triple\n");
	}
	return 0;
}

素数三元组(南阳oj1156)(素数水题)