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;}

代码解释

is_prime 函数：这个函数用于判断一个由字符串表示的数是否为素数。它处理了一些特殊情况，例如单个数字和以偶数或 5 结尾的数。对于其他情况，使用 Miller-Rabin 测试来判断是否为素数。

main 函数：读取输入，遍历所有可能的 K 位连续子串，对每个子串调用 is_prime 函数进行素数判断。如果找到素数，输出它；否则，输出 404。

通过这种方法，我们可以高效地找到最早出现的 K 位连续素数，或者确定其不存在。

转载地址：http://cor.baihongyu.com/

你可能感兴趣的文章