The 13th Blue Bridge Cup Competition C++ Graduate Group Exam Question B Super Prime Numbers

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

  1. Find prime numbers from 1 to n
  2. From the obtained prime numbers, find all substrings of the number
  3. 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;
}

  1. 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;
}

  1. 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

Leave a Comment

Your email address will not be published. Required fields are marked *