1094 谷歌的招聘

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

57148679-d574-4f49-b048-775c6c07791c.jpg

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

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

输入格式：

输入在第一行给出 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

源代码

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define TRUE 1
#define FALSE 0

// 将数组指定部分的字符转化为整数
long transfer(char arr[], int startIndex, int firstK)
{
    // 起始索引要小于或者等于结束索引
    if (startIndex <= startIndex + firstK - 1)
    {
        long temp = 0;
        // 将字符串转化为整数
        for (int i = startIndex, j = 0; j < firstK && i <= startIndex + firstK - 1; i++, j++)
        {
            // 整数字符的ASCII码介于字符0到字符9之间
            if (arr[i] < '0' && arr[i] > '9')
            {
                return -1;
            }
            temp += (arr[i] - '0') * pow(10, firstK - j - 1);
        }
        return temp;
    }
    return -1;
}

// 判断是否是素数
int isPrime(long num)
{
    if (num == 2)
    {
        return TRUE;
    }
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            return FALSE;
        }
    }
    return TRUE;
}

int main()
{

    //  length是输入的数长度，firstK是符合要求的素数的长度
    int length, firstK;

    scanf("%d %d", &length, &firstK);

    // 长度为length的数组 ，由于输入的数很长，已经超出了整数的表示范围，
    // 所以使用数组保存
    char *num = (char *)malloc(sizeof(char) * length);

    scanf("%s", num);

    // 从第一个字符开始将长度为 firstK的子串转化为 整数
    for (int i = 0; i < length; i++)
    {
        if (i + firstK - 1 < length)
        {
            long temp = transfer(num, i, firstK);
            //  如果是素数则直接范围并且不需要继续向下寻找
            if (isPrime(temp) == TRUE)
            {
                printf("%ld\n", temp);
                return 0;
            }
        }
    }

    printf("404");

    return 0;
}