PAT甲级——1152.Google Recruitment (20分)

flowchart 箭头图标 勿删

1152 Google Recruitment (20分)

In July 2004, Google posted on a giant billboard along Highway 101 in Silicon Valley (shown in the picture below) for recruitment. The content is super-simple, a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e. The person who could find this prime number could go to the next step in Google’s hiring process by visiting this website.

The natural constant e is a well known transcendental number（超越数）. The first several digits are: e = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642 7427466391 932003059921… where the 10 digits in bold are the answer to Google’s question.

Now you are asked to solve a more general problem: find the first K-digit prime in consecutive digits of any given L-digit number.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: L (≤ 1,000) and K (< 10), which are the numbers of digits of the given number and the prime to be found, respectively. Then the L-digit number N is given in the next line.

Output Specification:

For each test case, print in a line the first K-digit prime in consecutive digits of N. If such a number does not exist, output 404 instead. Note: the leading zeroes must also be counted as part of the K digits. For example, to find the 4-digit prime in 200236, 0023 is a solution. However the first digit 2 must not be treated as a solution 0002 since the leading zeroes are not in the original number.

Sample Input 1:

20 5
23654987725541023819

Sample Output 1:

49877

Sample Input 2:

10 3
2468024680

Sample Output 2:

404

这题是字符串的知识，故最近更新字符串的题目。

参考的柳婼的代码：

#include <iostream>
#include <string>
using namespace std;
bool isPrimeNumber(int a) // 判断是否是素数
{
    if(a == 0||a == 1) //首先排除0和1
        return false;
    for(int i = 2; i * i <= a; i++)//再次排除其他数
        if(a % i ==0)
            return false;
    return true;
}

int main() {
    int L,K;
    string s;
    cin >> L >> K >> s;
    for(int i = 0; i <= L-K; i++) {
        string t = s.substr(i, K); 		//截取字符串从 i 到i + K
        int num = stoi(t);			//将截取的字符串转化为数字
        if (isPrimeNumber(num)) {		//判断是否是素数
            cout << t;
            return 0;
        }
    }
    cout << "404\n";
    return 0;
}

题解中主要用到了 string 下的 substr 与 stoi 两个函数：

substr

用于截取字符串的某一段，用法如下：

string substr (size_t pos = 0, size_t len = npos) const;

Returns a newly constructed string object with its value initialized to a copy of a substring of this object.

The substring is the portion of the object that starts at character position pos and spans len characters (or until the end of the string, whichever comes first).

stoi

int stoi (const string&  str, size_t* idx = 0, int base = 10);
int stoi (const wstring& str, size_t* idx = 0, int base = 10);

Convert string to integer

将字符串转化为整型

Parses str interpreting its content as an integral number of the specified base , which is returned as an int value.

If idx is not a null pointer, the function also sets the value of idx to the position of the first character in str after the number.

The function uses strtol (or wcstol) to perform the conversion (see strtol for more details on the process).

类似的字符串转换成其他的函数还有

函数名	含义
stod	Convert string to double
stof	Convert string to float
stoi	Convert string to int
stol	Convert string to long int
stold	Convert string to long double
stoll	Convert string to long long
stoul	Convert string to unsigned integer
stoull	Convert string to unsigned long long
to_string	Convert numerical value to string
to_wstring	Convert numerical value to wide string

等，含义其实都是一个类型。将 string 转化为…