# PAT-A 真题 – 1152 Google Recruitment

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 . 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  is a well known transcendental number（超越数）. The first several digits are:  = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921... 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 <bits/stdc++.h>
using namespace std;

bool isPrime(int n){
if(n < 2) return false;
if(n == 2) return true;
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0) return false;
}
return true;
}

int main(){
int size, K;
string num;
cin >> size >> K >> num;
for(int i = 0; i <= size - K; i++){
string subs = num.substr(i, K);
int sub = stoi(subs);
if(isPrime(sub)){
while(subs.size() < K) subs = '0' + subs;
cout << subs << endl;
return 0;
}
}
cout << 404 << endl;
return 0;
}