[C++知识库]PTA甲级 1152 Google Recruitment (C++)

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 $e$. The person who could find this prime number could go to the next step in Google’s hiring process by visiting this website.

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.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: $L(\le 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:

49877

Sample Input 2:

10 3
2468024680

Sample Output 2:

404

Solution:

// Talk is cheap, show me the code
// Created by Misdirection 2021-08-30 21:45:46
// All rights reserved.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool isPrime(int a){
    if(a <= 1) return false;
    if(a <= 3) return true;

    for(int i = 2; i <= sqrt(a); ++i){
        if(a % i == 0) return false;
    } 
    return true;
}

int main(){
    int l, n;
    scanf("%d %d", &l, &n);
    string s;
    cin >> s;

    for(int i = 0; i < l + 1 - n; ++i){
        string tmp = s.substr(i, n);

        int t = stoi(tmp);
        if(isPrime(t)){
            printf("%s\n", tmp.c_str());
            return 0;
        }
    }

    printf("404\n");

    return 0;
}