素数三元组-南阳OJ1156（高效打表筛选）

我会带着你远行 2022-06-01 03:42 100阅读 0赞

## 素数三元组 ##

时间限制：1000 ms | 内存限制：65535 KB

难度：1

描述

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

看到这道题，思路无非就是把数一个一个测，而且也在意料之中超时，因为测试数据很大很大。所以要么找规律，要么尽可能压缩算法时间。

我介绍第二种方法，打表筛选压缩算法时间。

代码主要理解**continue**的优点，通过提前排除避免深度循环，然后同时测三个数并做好标记，在两个continue的跳过下能执行到最后的就是一组解，储存。

代码如下：

/*素数三元，2017/12/28 by SZU-Crayon*/ 
    #include<bits/stdc++.h>
    #define N 5000000
    using namespace std;
    int num[N]={0};   //初始化表 
    int result[5][5]; 
    int n;
    int i,j;
    int cnt=0,cnt1=0;
    void Thepresolve() {
    	for(i=4; i<=N-2; i++) 
    	{
    		if(num[i-2]==1||num[i]==1||num[i+2]==1)     //1表示非素数，三个相邻只要有一个非素数就跳过本次循环 
    			continue;
    
    		for(j=2; j<=sqrt(i+2); j++)               //一次检验三个相邻数，一个非就跳出循环 
    			if( !((i+2)%j) || !((i-2)%j) || !(i%j) )
    				break;
    		if(j<=sqrt(i+2))        //非正常结束循环（break出来的）执行 ，把非素数标记为1 
    		{
    			if(!((i+2)%j))
    				num[i+2]=1;
    			if(!(i%j))
    				num[i]=1;
    			if(!((i-2)%j))
    				num[i-2]=1;
    			continue;
    		}
    		//能走到最后的把结果储存 
    		result[++cnt][1]=i-2;
    		result[cnt][2]=i;
    		result[cnt][3]=i+2;
    	}
    }
    
    int main() {
    	Thepresolve();  //提前处理 
    	/*cout<<cnt<<endl;
    	for(i=1;i<=cnt;i++)
    		cout<<result[cnt][1]<<" "<<result[cnt][2]<<" "<<result[cnt][3]<<endl;*/
    	while(cin>>n){
    		cnt1=0;
    		for(j=1;j<=cnt;j++)
    			if(result[j][3]<=n){         //确定输出边界 
    				cnt1++;
    				cout<<result[cnt][1]<<" "<<result[cnt][2]<<" "<<result[cnt][3]<<endl;
    			}
    		if(!cnt1)
    			cout<<"No triple"<<endl;
    	}
    	return 0;
    }

输入

输入多组数据，每组测试数据为一个正整数n，***n <= 5000000。***

输出

输出大小不超过n的所有的素数三元组，每行按照从小到大的顺序输出一个三元组中的三个数，两个数之间用空格间隔。如果不存在这样的素数三元组，请输出“No triple”。

样例输入

样例输出

No triple