2022 团体程序设计天梯赛 模拟赛 1-8 均是素数 (20 分)

在给定的区间 [m,n] 内，是否存在素数 p、q、r（p<q<r），使得 pq+r、qr+p、rp+q 均是素数？

输入格式：

输入给出区间的两个端点 0<m<n≤1000，其间以空格分隔。

输出格式：

在一行中输出满足条件的素数三元组的个数。

输入样例：

1 35

输出样例：

10

样例解读

满足条件的 10 组解为：

2, 3, 5
2, 3, 7
2, 3, 13
2, 3, 17
2, 5, 7
2, 5, 13
2, 5, 19
2, 5, 31
2, 7, 23
2, 13, 17

 好题！模拟赛的时候没注意到关键剪枝，但是也过了。详细说一下思路

首先1000以内最大的两个素数是991和997，差不多是10^6的量级，因此，需要对素数提前打表。

为了提高查询速度，再额外附加一个数组作为快表使用。笔者使用了质数筛+平方根判别。

再之后就是遍历了，此处有一个关键性的剪枝：如果是三个奇数参与题中所给的三元操作，其结果为偶数，必不为素数。由于2是唯一的素数，因此，先判别范围是否包含2，在存在2的前提下，进行二重循环就可以了。

#include <bits/stdc++.h>
using namespace std;
int v[1000000]={0};						//素数快表 
int main(void){
	int m,n,sum=0;
	vector<int> p;						//素数表
	vector<int> d;						//检查序列 
	p.push_back(2);
	cin>>m>>n;
	for(int i=3;i<1000000;i+=2){
		int flg=1;
		for(int j=0;j<p.size();j++){
			if(i<p[j]*p[j])break;
			if(!(i%p[j])){
				flg=0;
				break;
			}
		}
		if(flg){
			v[i]=1;
			p.push_back(i);
		}
	} 
	for(int i=0;i<p.size();i++){		 
		if(p[i]>n)break;
		if(p[i]>=m)d.push_back(p[i]); 
	}
	if(d[0]==2)							//剪枝
	for(int i=1;i<d.size()-1;i++){
		for(int j=i+1;j<d.size();j++){
				int a=d[i],b=d[j];
				if(v[a*b+2]&&v[a*2+b]&&v[b*2+a])sum++;
		}
	}
	cout<<sum;
	return 0;
}