2022 group programming ladder simulation match 1-8 are prime numbers (20 points)

In a given interval  [m,n]  Inside , Is there a prime  p、q、r（p<q<r）, bring  pq+r、qr+p、rp+q  Are prime numbers ？

Input format ：

Enter the two endpoints of the given interval  0<m<n≤1000, Separated by spaces .

Output format ：

Output the number of prime triples that meet the conditions in one line .

sample input ：

1 35

sample output ：

10

Example interpretation

Satisfied 10 Group solution is ：

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

  Good question ！ I didn't notice the key pruning during the simulation , But it's over . Explain the idea in detail

First 1000 The two largest primes within are 991 and 997, Is almost 10^6 The magnitude of , therefore , You need to make a table of prime numbers in advance .

To improve query speed , Add an additional array to use as a fast table . The author uses the prime number sieve + Square root discrimination .

Then it's traversal , Here's a key pruning ： If it is three odd numbers, participate in the ternary operation given in the question , The result is an even number , Must not be prime . because 2 Is the only prime number , therefore , First determine whether the scope includes 2, In existence 2 Under the premise of , Just double cycle .

#include <bits/stdc++.h>
using namespace std;
int v[1000000]={0};						// Prime fast table  
int main(void){
	int m,n,sum=0;
	vector<int> p;						// Prime table 
	vector<int> d;						// Check the sequence  
	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)							// prune 
	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;
}