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 $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.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 ( $\leq$ 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:

Sample Input 2:

10 3
2468024680

Sample Output 2:

题目大意：从题目所给的L位数字中找到连续的K位数字，要求这个数字是质数，并输出。如果找不到。输出404。

这道题简单的模拟一下就行。注意求质数时的判断条件必须是i < sqrt(num)，如果是i<num或i<num/2，最后一个测试点会超时。

#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;
}

斐斐のBlog