PAT乙级 | 1094 谷歌的招聘 (20分)-白红宇

PAT乙级 | 1094 谷歌的招聘 (20分)

阅读量：86 次

发布时间：2019-02-26

本文共 1204 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要从给定的一个长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。如果不存在这样的素数，我们则输出 404。

方法思路

输入处理：读取输入的两个正整数 L 和 K，然后读取一个长度为 L 的正整数 N。

遍历子串：遍历 N 的所有可能的 K 位连续子串。

素数判断：对于每个子串，判断其是否为素数。这里我们需要处理大数情况，因此使用字符串处理来判断是否为素数。

输出结果：如果找到素数，输出它；否则，输出 404。

解决代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;bool is_prime(string s) {    if (s.size() == 1) {        return (s == "2");    }    if (s.back() == '0' || s.back() == '5') {        return (s == "2");    }    long long n = stoll(s);    if (n <= 1) return false;    if (n <= 3) return true;    if (n % 2 == 0) return false;    long long sqrt_n = sqrt(n);    for (long long i = 3; i <= sqrt_n; i += 2) {        if (n % i == 0) return false;    }    return true;}int main() {    string N;    int L, K;    cin >> L >> K;    cin >> N;    for (int i = 0; i <= L - K; ++i) {        string s = N.substr(i, K);        if (is_prime(s)) {            cout << s;            return;        }    }    cout << "404";    return;}