pat 1152

1152 Google Recruitment (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 e is a well known transcendental number（超越数）. The first several digits are: e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921... where the 10 digits in bold are the answer to Google's question.

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 (≤ 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:

题意：求一个给定字符串中最先的连续k位的素数，如果不存在返回404

思路：字符数组存储字符串，设置一个指向第一个字符的变量，依次检测从该地方起的k位是否是素数。

注意点：有些素数以0开头，输出的时候前面的0不能省略，而素数的位数根据k来确定，但k又是输入进来的，因此这里需要特殊处理下

代码如下

#include<cstdio>
#include<math.h>
char num[1005];
bool isPrime(int sum){
    int mark=0;
    for(int i=2;i<sqrt(sum);i++){
        if(sum%i==0){
            mark=1;
            break;
        } 
    }
    if(mark==1)
        return false;
    else
        return true; 
}
long long fun(int i,int k){
    long long sum=0;
    for(int j=i;j<k+i;j++){
        sum=sum*10+num[j]-'0'; 
    }
    if(isPrime(sum))
        return sum;
    else
        return -999999l;
}
int main(){
    int l,k;
    long long ans;
    scanf("%d%d",&l,&k);
    scanf("%s",num);
    int mark=0;
    for(int i=0;i<l-k+1;i++){
        if(fun(i,k)!=-999999l){
            mark=1;
            
            ans=fun(i,k);
            break;
        }
    }
    if(mark==0)
        printf("404");
    else{
        int size=0;
        long long temp=ans;
        while(temp!=0){
            temp/=10;
            size++;
        }
        if(size!=k){
            for(int i=0;i<k-size;i++){
                printf("0");
            }
        }
        printf("%d",ans);
    }
    return 0;
}