谷歌的招聘

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

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

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

时间限制：7000

内存限制：65535

输入

输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于10的正整数）。接下来一行给出一个长度为 L 的正整数 N。

输出

在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出“404”。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

样例输入

样例1：

20 5
23654987725541023819

样例2：

10 3
2468024680

样例输出

样例1：

49877

样例2：

404

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

bool is_prime(int num); // 判断是否为素数的函数声明

int main() {
    int L, K; // 数字长度和连续数字位数
    scanf("%d %d", &L, &K); // 输入数字长度和连续数字位数
    char num[L + 1]; // 存储输入的数，多加一个字符用于存储字符串结束符'\0'
    scanf("%s", num); // 输入数字字符串
    int start = 0; // 从数字字符串的起始位置开始查找连续的K位数字
    while (start + K <= L) { // 当找到的数字长度大于等于K位时继续查找
        int num_K = atoi(num + start); // 将找到的K位数字转换为整数
        if (is_prime(num_K)) { // 如果找到的K位数字是素数，则输出并结束程序
            printf("%d", num_K);
            return 0;
        }
        start++; // 未找到素数，继续查找下一个K位数字
    }
    printf("404"); // 未找到符合条件的素数，输出404
    return 0;
}

bool is_prime(int num) { // 判断一个数是否为素数
    if (num < 2) return false; // 小于2的数不是素数
    int sqrt_num = sqrt(num); // 素数一定小于等于它的平方根，只需判断到它的平方根即可
    for (int i = 2; i <= sqrt_num; i++) { // 判断num是否为素数
        if (num % i == 0) return false; // 存在因子则不是素数
    }
    return true; // 没有因子则是素数
}

本题要求从给定的数字中找到最早出现的连续K位数字组成的素数。解题的关键在于两个步骤：一是找到连续K位数字，二是判断这个K位数字是否为素数。因此，我们可以使用字符串操作函数和数学函数来实现这个功能。具体步骤如下：首先读取输入的数字长度L和连续数字位数K，然后读取具体的数字字符串。使用一个循环来遍历数字字符串，每次取出连续K位数字并转换为整数进行判断。判断一个数是否为素数可以使用简单的算法：从2开始判断是否能被整除到它的平方根，如果存在因子则不是素数。在程序中，我们定义了一个is_prime函数来实现素数的判断。如果找到了符合条件的素数，则输出并结束程序；如果没有找到符合条件的素数，则输出404。注意在判断连续K位数字时，由于可能存在前导零，因此我们需要将找到的数转换为整数进行判断。