PAT甲级 1152. Google Recruitment

前言

这道题是跟素数相关的,我发现PAT甲级第一题很喜欢考素数啊,出现过很多次了,不过都没办法难……

题目原文

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 (≤ 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

解决思路

给定一个L位的数字,找到一个K位的素数。
每K位为一个单位进行遍历,判断数字是否是素数,是则输出,不是则继续,最终没找到就输出404。需要注意的就是输入数字是个字符串大数,要局部转换成K位数字进行计算,然后使用经典素数判断算法即可。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>

using namespace std;

bool isPrime(string str) {
int str_int = stoi(str);
for(int i = 2; i <= pow(str_int, 0.5); i++) {
if(str_int % i == 0) {
return false;
}
}
return true;
}

int main(void) {
int L, K;
string input;
cin >> L >> K >> input;

if(input.length() < K) {
cout << "404";
} else {
for(int i = 0; i <= input.length() - K; i++) {
string sub = input.substr(i, K);
if(isPrime(sub)) {
cout << sub;
return 0;
}
}
cout << "404";
}
return 0;
}

##