PAT Basic Level 1094 谷歌的招聘 （20 分）

题目链接:

https://pintia.cn/problem-sets/994805260223102976/problems/1071785997033074688

我的17分代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstdlib>

using namespace std;

bool isPrime(int n){
    float n_sqrt;
    if(n==2||n==3)  return true;
    if(n%6!=1&&n%6!=5)  return false;
    n_sqrt=floor(sqrt((float)n));
    for(int i=5;i<=n_sqrt;i+=6){
        if(n%i==0 | n%(i+2)==0)
            return false;
    }
    return true;
}


int main()
{
    int L,K;
    int flag=0;
    scanf("%d%d",&L,&K);
    string str;
    cin>>str;
    for(int i=0;i<str.size()-K-1;i++){//str.size()-K,测试点5出错
        string str_=str.substr(i,K);
        int a=atoi(str_.c_str());
        if(isPrime(a)){
            cout<<str_;
            flag=1;
            break;
        }
    }
    if(!flag)
        printf("404");
    return 0;
}
           

AC代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstdlib>
#include <sstream>
#include <algorithm>

using namespace std;

bool isPrime(long long n){
    float n_sqrt;
    if(n==2||n==3)  return true;
    if(n%6!=1&&n%6!=5)  return false;
    n_sqrt=floor(sqrt((float)n));
    for(int i=5;i<=n_sqrt;i+=6){
        if(n%i==0 | n%(i+2)==0)
            return false;
    }
    return true;
}

int main()
{
    int L,K;
    int flag=0;
    scanf("%d%d",&L,&K);
    string str;
    cin>>str;
    for(int i=0;i<=L-K;i++){//测试点2:i<=L-K;而非i<=L-K-1
    //测试点4:判断循环终止条件:应该是L-K，而不是str.size()-1.
        string str_=str.substr(i,K);
        stringstream ss;
        long long res;
        ss<<str_;
        ss>>res;
        ss.clear();
        if(isPrime(res)){
            cout<<str_;
            flag=1;
            break;
        }
    }
    if(!flag)
        printf("404");
    return 0;
}
           

 二刷:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int n){
    if(n<=1)    return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++){
        if(n%i==0)
            return false;
    }
    return true;
}

int main(){
    int L,K;
    string str;
    scanf("%d%d",&L,&K);
    getchar();
    getline(cin,str);
    int i;

    for(i=0;i+K<=str.size();i++){
      string tmp=str.substr(i,K);
      int num=0;
      num=atoi(tmp.c_str());
      if(isPrime(num)){
        cout<<tmp;//输入的数字中找的素数是00023这种，输出也要输出00023（测试点2）
                  //所以只能用cout<<tmp输出，而不是printf("%d",num);
        return 0;
      }
    }
    
    //不加if(i+K>=L),测试点5通过
    printf("404");
    return 0;
}