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

在给定的区间 [m,n] 内，是否存在素数 p、q、r（p 输入格式：

输入给出区间的两个端点 0 输出格式：

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

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 
using namespace std;
int v[1000000]={0};						//素数快表 
int main(void){
	int m,n,sum=0;
	vector p;						//素数表
	vector d;						//检查序列 
	p.push_back(2);
	cin>>m>>n;
	for(int i=3;i<1000000;i+=2){
		int flg=1;
		for(int j=0;jn)break;
		if(p[i]>=m)d.push_back(p[i]); 
	}
	if(d[0]==2)							//剪枝
	for(int i=1;i