2024 年 6 月青少年软编等考 C 语言三级真题解析

T1. 谷歌的招聘

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单，就是一个以 $. co m$ 结尾的网址，而前面的网址是一个 $10$ 位素数，这个素数是自然常数 $e$ 中最早出现的 $10$ 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 $e$ 是一个著名的超越数，前面若干位写出来是这样的： $e =$ 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 $10$ 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 $L$ 的数字中，找出最早出现的 $K$ 位连续数字所组成的素数。

时间限制：1 s
内存限制：64 MB

输入
输入在第一行给出 $2$ 个正整数，分别是 $L$ （不超过 $1000$ 的正整数，为数字长度）和 $K$ （小于 $10$ 的正整数）。
接下来一行给出一个长度为 $L$ 的正整数 $N$ 。
输出
在一行中输出 $N$ 中最早出现的 $K$ 位连续数字所组成的素数。如果这样的素数不存在，则输出 $404$ 。注意，原始数字中的前导零也计算在位数之内。例如在 $200236$ 中找 $4$ 位素数， $0023$ 算是解；但第一位 $2$ 不能被当成 $0002$ 输出，因为在原始数字中不存在这个 $2$ 的前导零。
样例输入 1
```
20 5
23654987725541023819
```
样例输出 1
```
49877
```
样例输入 2
```
10 3
2468024680
```
样例输出 2
```
404
```

思路分析

此题考查枚举法与素数判断，属于入门题。

我们可以从前向后枚举需要截取的子串的起点 $i$ ，从 $i$ 开始截取长度为 $K$ 的子串，并将其转换为整数 $n u m$ 。接着判断该整数是否为素数即可。为了避免越界，枚举的终点应为 $L - K$ 。注意最后输出的是长度为 $K$ 的子串，而不是去除前导零之后的 $n u m$ 。

/** Name: T1.cpp* Problem: 谷歌的招聘* Author: Teacher Gao.* Date&Time: 2025/02/08 17:24*/#include <iostream>
#include <string>using namespace std;bool prime(int k) {if (k < 2) return 0;for (int i = 2; i*i <= k; i++) {if (k % i == 0) return 0;}return 1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int L, K;string s;cin >> L >> K >> s;for (int i = 0; i <= L - K; i++) {int num = stoi(s.substr(i, K));if (prime(num)) {cout << s.substr(i, K) << endl;return 0;}}cout << 404 << endl;return 0;
}