“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

2,3,5,7,11,13,… Is a sequence of prime numbers. Similar: 7,37,67,97,127,157 such a complete composition of prime arithmetic sequence, called arithmetic prime sequence.

The tolerance of the above sequence is 30 and the length is 6.

In 2004, Green, in collaboration with Tao Zhexuan, proved that there exists an arithmetic sequence of prime numbers of any length. This is an amazing achievement in the field of number theory!

With this theory in mind, search with confidence on your computer:

What is the minimum tolerance of an arithmetic prime column of length 10?

Two, the title requirements

Operating limits

  • Maximum running time: 1s
  • Maximum running memory: 128M

Third, problem analysis

First, a prime number is a number that is divisible only by 1 and itself. Construct a separate function to store primes up to 6000 into an array.

For such a blank filling problem, the length of arithmetic sequence is only 10, so there is no need to use deep search DFS or other methods, only the violence method can also quickly calculate the result.

The main function uses a triple for loop. The first layer is all the primes stored in the array, the second layer is the tolerance of the arithmetic sequence, and the third layer is 10 prime numbers that meet the conditions. If a[I]+j*k is still a prime number, after 10 judgments, it is still true, then output the tolerance j of the current position, the current tolerance is the result of the request.

Four, coding implementation

#include<iostream>
#include<math.h>// The header file contains SQRT square root
using namespace std;
bool judge(int n)// Check whether it is prime
{
	int i;
	for(i=2; i<=sqrt(n); i++)// Use the square root to reduce the amount of data
	{
		if(n%i==0)
			return false;// Return error
	}
	return true;// Return correct
}
int main(a)
{
	int i,j,k,length=0,a[5000],sum=0;// Define the length of the array
	for(i=2; i<6000; i++)// Loop through all primes up to 6000
	{
		if(judge(i))/ / is a prime number
		{
			a[length++]=i;// Store to array}}for(i=0; i<length; i++)// Loop the first layer
	{
		for(j=1; j<500; j++)// The second loop
		{
			sum=0;/ / initial value
			for(k=0; k<10; k++)// The third layer for loop
			{
				if(judge(a[i]+j*k))// Determine the next 10 numbers
				{
					sum++;// Meet the criteria}}if(sum==10)// Successfully found
			{
				cout<<j;// Output tolerance
				exit(0);// Exit the loop}}}return 0;
}
Copy the code

5. Output results

The specific result is: 210