PAT(Advanced)1152 Google Recruitment (20 分)

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

题目解读：找多少位数里前k位是素数，并把它打出来，如果不存在则打印404。考虑前导0的存在也要打印出来。

解题思路：乙级的题，坑会设在输出上。比如在output里给了一个200236的例子，要把0也打印出来。学会了一个新的表达方式 printf("%0*d",k,sum); 表示k位数字，不满高位补0。

bug点在循环上，我的循环走最外层时 0~len-n，应该是0~len-n+1。这是为啥呢，因为我要走到距离最后一位还有n的时候停下来，比如我的len是10，n是3，那么我需要走到第7个的时候停下来，如果是0~len-n的话，第7个其实是取不到的，所以需要0~len-n+1，这样可以取到7。

AC代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool isprime(int num) {
	if (num == 1)return false;
	if (num == 2) return true;
	for (long long i = 2; i < (int)sqrt(num) + 1; i++) {
		if (num % i == 0) return false;
	}
	return true;
}
int main()
{
	string s;
	int len;
	int n;
	cin >> len >> n >> s;
	for (int i = 0; i < len - n +1; i++) {
		int sum = 0;
		sum = stoi(s.substr(i,n));
		if (isprime(sum)) {
			printf("%0*d", n, sum);
			return 0;
		}
	}
	cout << "404" << endl;
	return 0;
}