首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7506

谷歌的招聘 2004年7月,谷歌在硅谷的101号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单,就是一个以 .com 结尾的网址,而前面的网址是一个 10…

谷歌的招聘

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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include&lt;bits/stdc++.h&gt; using namespace std; bool prime(int num) {     if(num &lt;= 1)         return false;     for(int i=2; i&lt;=sqrt(num); i++)     {         if(num%i == 0)             return false;     }     return true; } int main() {     int L,K;     string str;     cin&gt;&gt;L&gt;&gt;K&gt;&gt;str;     bool flag = false;//没有找到的标记     for(int i=0; i&lt;=L-K; i++)     {      //提取字符串         string temp(str,i,K);         //转成数字         stringstream ss(temp);         int num;         ss&gt;&gt;num;         //判断         if(prime(num))         {             flag = true;             cout&lt;&lt;temp;             break;         }     }     if(!flag)         cout&lt;&lt;"404";     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; int isPrime(long long n) {     if (n &lt; 2) {         return 0;     }     for (long long i = 2; i * i &lt;= n; i++) {         if (n % i == 0) {             return 0;         }     }     return 1; } int main() {     int l, k;     scanf("%d %d", &amp;l, &amp;k);     char s[1001];     scanf("%s", s);     int pos = 0;     for (int i = 0; i &lt;= l - k; i++) {         char w[11];         strncpy(w, s + i, k);         w[k] = '\0';         long long ans = atoll(w);         if (isPrime(ans)) {             printf("%s", w);             return 0;         }         pos++;     }     printf("404");     return 0; }</pre>
这道题暂未补解析。