PAT甲级——A1152 GoogleRecruitment【20】

In July 2004, Google posted on a giant billboard along Highway 101 in Silicon Valley (shown in the picture below) for recruitment. The content is super-simple, a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant

The natural constant

Now you are asked to solve a more general problem: find the first K-digit prime in consecutive digits of any given L-digit number.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: L ( $\leq 1,000) and K (< 10), which are the numbers of digits of the given number and the prime to be found, respectively. Then the L-digit number N is given in the next line.$

Output Specification:

For each test case, print in a line the first K-digit prime in consecutive digits of N. If such a number does not exist, output 404 instead. Note: the leading zeroes must also be counted as part of the K digits. For example, to find the 4-digit prime in 200236, 0023 is a solution. However the first digit 2 must not be treated as a solution 0002 since the leading zeroes are not in the original number.

Sample Input 1:

20 5
23654987725541023819

Sample Output 1:

Sample Input 2:

10 3
2468024680

Sample Output 2:

404

Solution：
　　这道题令我惊讶的是，竟然是简单的判断一下是不是素数？！
　　本以为这么大的数字级别，应该是建立素数表来判断的，想不到竟然时一个个数字进行简单的判断是不是素数？
　　倒是建立素数表内存超了，判断是不是素数竟然没有超时？！
　　下面代码给出了建立素数表

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <cmath>
 5 using namespace std;
 6 int n, k;
 7 string str, res = "";
 8 //void getPrimeTable(int inf, vector<bool>&notPrime)//创建素数表
 9 //{
10 //    notPrime[0] = notPrime[1] = true;
11 //    for (int i = 2; i <= inf; ++i)
12 //        if (notPrime[i] == false)//从2这个素数开始
13 //            for (int j = 2; j*i <= inf; ++j)
14 //                notPrime[j*i] = true;//剔除素数的所有倍数
15 //}
16 
17 bool isPrime(int x)//判断是不是素数
18 {
19     if (x < 3)
20         return true;
21     for (int i = 2; i*i <= x; ++i)
22         if (x%i == 0)
23             return false;
24     return true;
25 }
26 int main()
27 {
28     cin >> n >> k;
29     cin >> str;
30     //int size = (int)pow(10, k);
31     //vector<bool>notPrime(size+1, false);//防止内存太大，我这里是动态建立数组的
32     //getPrimeTable(size, notPrime);//创建素数表
33     for (int i = 0; i + k <= n; ++i)
34     {
35 
36         string s = str.substr(i, k);
37         int num = atoi(s.c_str());
38         if (isPrime(num))//notPrime[num]==false)//使用的代码简单的素数判断，注释的代码是使用素数表
39         {
40             res = s;
41             break;
42         }
43     }
44     if (res.size() > 0)
45         cout<<res;
46     else
47         cout << "404";
48     return 0;
49 }