### Article directory

# foreword

This article is the subject of the second C++ postgraduate group of the 13th [Blue Bridge Cup] Software Competition Provincial Competition. Each question will be summarized and recorded in turn. The ability is limited. If there is a better solution, please do not hesitate to enlighten me.

# topic

If each digit of a prime number P is a prime number, and every two adjacent digits formed by two

digits are prime, and every three adjacent digits formed by three digits are prime, and so on, if each phase

If the k-digits formed by the adjacent k-digits are all prime numbers, then P is called a super prime number.

If the super prime number P is regarded as a string, then every substring of this super prime number is a prime

number.

For example, 53 is a super prime number.

Excuse me, what is the largest super prime number?

# Problem solving ideas

The definition of a super prime number in this question is that every substring of the number is a prime number, for example

The number 2375

then the substring of the number is: 2, 3, 7, 5, 23, 37, 75, 237, 375, 2375

When all the substrings above are prime numbers, then the number is a super prime number.

Then the steps to solve the problem are as follows

- Find prime numbers from 1 to n
- From the obtained prime numbers, find all substrings of the number
- Judging all substrings in turn, if a substring is not a prime number, return to step 1 to find the next prime number.

## 1. Find prime numbers

To determine whether a number is a prime number, the conventional method is to determine whether the number is divisible by a number smaller than itself.

code show as below:

bool Prime_Number_Judge ( const int &num) { if (num <= 3 ) //Judge whether it is less than 3 { return num > 1; } for ( size_t i = 2 ; i < num; i++) //Determine whether it can be divisible by a number less than itself { if (num % i == 0) { return false ; } } return true; }

However, in fact, if a number is not a prime number, there must be some divisor, which is greater than sqrt(num) and less than sqrt(num) respectively, then we only need to judge whether the number is divisible by the number less than sqrt(num).

Then the code is changed to the following:

bool Prime_Number_Judge ( const int &num) { if (num <= 3 ) //Judge whether it is less than 3 { return num > 1; } for ( size_t i = 2 ; i < sqrt (num); i++) //Determine whether it can be divisible by a number less than sqrt(num) { if (num % i == 0) { return false ; } } return true; }

If a number is not divisible by 2, it must not be divisible by other even numbers, because any even number can be divided by 2*n. Then we only need to judge whether it is divisible by an odd number less than sqrt(num). The

code is optimized as:

bool Prime_Number_Judge ( const int &num) { if (num <= 3 ) //Judge whether it is less than 3 { return num > 1; } if ( num % 2 == 0 ) //Determine whether it can be divisible by 2 { return false ; } for ( size_t i = 3 ; i < sqrt (num); i+= 2 ) //Determine whether it is divisible by an odd number less than sqrt(num) { if (num % i == 0) { return false ; } } return true; }

Furthermore, for prime numbers greater than 5, it must be 6 *X-1 or 6* X+1. Take advantage of this feature. Integers can be filtered to determine whether only those integers that are 6x-1 or 6x-1 are prime numbers.

Proof:

Let x≥1, then the natural numbers greater than or equal to 5 are expressed as follows: Adjacent 6 numbers are a group)

6x, 6x+2, 6x+4 can be divisible by 2, 6x+3 can be expressed as 3*(2x+1), which can be divisible by 3, leaving only 6x-1 and There may be prime numbers in 6x+1. So the prime number must be 6x-1 or 6x+1.

The code optimization is as follows:

bool Prime_Number_Judge ( const int &num) { if (num <= 3 ) //Judge whether it is less than 3 { return num > 1; } if (num % 6 != 1 && num % 6 != 5 ) //Determine whether it is 6x-1 or 6x+1 { return false ; } if ( num % 2 == 0 ) //Determine whether it can be divisible by 2 { return false ; } for ( size_t i = 3 ; i < sqrt (num); i+= 2 ) //Determine whether it is divisible by an odd number less than sqrt(num) { if (num % i == 0) { return false ; } } return true; }

## 2. Find all substrings

Divided into three steps

1. Find the total number of digits, such as: 1 means 1 digit, 53 means 2 digits, and 2373 means 4 digits

// Find how many digits in a number int & Get_Number_Size ( const int &num) { int digit = 0 ; int val = num; while (val) { val /= 10; digit++; } return digit; }

- Represent each digit of the number with an array, such as 2372, then create an array [2,3,7,3]

vector<int>& Get_Digits(const int &num , vector<int> &digits) { //Represent each digit of the number as an array int vactor_val = 0 ; //Use Get_Number_Size() to find the number of digits, and calculate the remainder and division for ( size_t num_size = Get_Number_Size(num); num_size > 0 ; num_size--) { vactor_val = num % (int)pow(10.0, num_size); vactor_val = vactor_val /(int)pow(10.0, num_size - 1); digits.push_back(vactor_val); } return digits; }

- Use the loop to find each substring of the number

vector<int>& Get_K_Adjacent(const int &num, vector<int> &adjacent) { vector < int > digists_number; // Each digit of the number is represented by an array, and there is an array digists_number Get_Digits(num , digists_number); //find the number length int digits = Get_Number_Size(num); for ( size_t i = 0 ; i < digits; i++) { for (size_t j = 0; j < digits-i ; j++) { string buf; int k = 0; while (k <= i) { //Use the += operator of the string to concatenate substrings buf += to_string(digists_number.at(j + k)); k++; } //Then convert the concatenated substring into an integer, and there is an array adjacent adjacent.push_back(stoi(buf)); } } return adjacent; }

## 3. Judge all substrings in turn. If a substring is not a prime number, return to step 1 to find the next prime number.

So far all the work has been completed, use the for loop to traverse the numbers in turn, and find the super prime numbers among the prime numbers.

The full code is as follows:

#include <iostream> #include <string> #include <vector> using namespace std; //Determine whether a number is a prime number, return true if it is, if not return false bool Prime_Number_Judge ( const int &num) { if (num <= 3 ) //Determine whether it is less than 3 { return num > 1; } if (num % 6 != 1 && num % 6 != 5 ) //Determine whether it is 6x-1 or 6x+1 { return false ; } if (num % 2 == 0 ) //Determine whether it is divisible by 2 { return false ; } for ( size_t i = 3 ; i < sqrt (num); i += 2 ) //Determine whether it can be divisible by a number smaller than itself { if (num % i == 0) { return false ; } } return true; } // Find how many digits in a number int & Get_Number_Size ( const int &num) { int digit = 0 ; int val = num; while (val) { val /= 10; digit++; } return digit; } //Return all digits of a number vector < int >& Get_Digits( const int &num , vector < int > &digits) { int vactor_val = 0 ; //Use Get_Number_Size() to find the number of digits, and perform remainder and integer division calculations for ( size_t num_size = Get_Number_Size(num); num_size > 0 ; num_size--) { vactor_val = num % (int)pow(10.0, num_size); vactor_val = vactor_val /(int)pow(10.0, num_size - 1); digits.push_back(vactor_val); } return digits; } //Find all substrings vector < int >& Get_K_Adjacent( const int &num, vector < int > &adjacent) { vector < int > digists_number; // Each digit of the number is represented by an array, and there is an array digists_number Get_Digits(num , digists_number); int digits = Get_Number_Size(num); for (size_t i = 0; i < digits; i++) { for (size_t j = 0; j < digits-i ; j++) { string buf; int k = 0; while (k <= i) { //Use the += operator of the string to concatenate substrings buf += to_string(digists_number.at(j + k)); k++; } //Then convert the concatenated substring into an integer, and there is an array adjacent adjacent.push_back(stoi(buf)); } } return adjacent; } int main () { //Check whether 1-10000 is a prime number in turn for ( size_t i = 1 ; i < 10000 ; i++) { if (Prime_Number_Judge(i)) { //Check for super primes in the resulting primes vector < int > buf; Get_K_Adjacent(i, buf); //sign is used as a marker to mark whether there are non-prime numbers in the substring, if so, set it to 0 int sign = 1 ; for ( size_t j = 0 ; j < buf.size(); j++) { if (!Prime_Number_Judge(buf.at(j))) { //When a non-prime number occurs, the sign is set to 0 sign = 0 ; break ; } } if (sign) { cout << i << "is super_prime_number" << endl; } } } return 0; }

The final running result is:

So the answer to this question is 373. Congrats on completing the first question!

# Note:

The reference for the idea of finding prime numbers comes from the blogger: Jeff’s article, the link is here , the original text has a more detailed explanation