PAT甲级1168题（素数日）

字符串处理题

PAT

发布日期: 2021-02-11

文章字数: 356

阅读时长: 2 分

阅读次数:

1.题目介绍

The above picture is from Sina Weibo, showing May 23rd, 2019 as a very cool “Prime Day”. That is, not only that the corresponding number of the date 20190523 is a prime, but all its sub-strings ended at the last digit 3 are prime numbers.

Now your job is to tell if a given date is a Prime Day.

Input Specification:

Each input file contains one test case. For each case, a date between January 1st, 0001 and December 31st, 9999 is given, in the format yyyymmdd.

Output Specification:

For each given date, output in the decreasing order of the length of the substrings, each occupies a line. In each line, print the string first, followed by a space, then Yes if it is a prime number, or No if not. If this date is a Prime Day, print in the last line All Prime!.

Sample Input 1:

20190523

Sample Output 1:

20190523 Yes
0190523 Yes
190523 Yes
90523 Yes
0523 Yes
523 Yes
23 Yes
3 Yes
All Prime!

Sample Input 2:

20191231

Sample Output 2:

20191231 Yes
0191231 Yes
191231 Yes
91231 No
1231 Yes
231 No
31 Yes
1 No

2.考察点，难度

字符串处理类，string转int，素数判定方法，难度易

3.解题代码

#include <iostream>
#include <string>
using namespace std;

int isPrime(string s){
    int a = stoi(s);
    if(a==0||a==1)  return 0;
    if(a==2)  return 1;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)  return 0;
    }
    return 1;
}

int main(){
    string s;
    cin>>s;
    int l=s.length(),flag=1;
    for(int i=0;i<l;i++){
        cout<<s<<" ";
        if(isPrime(s)==1){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
            flag=0;
        }
        s = s.substr(1,s.length()-1);
    }
    if(flag) cout<<"All Prime"<<endl;

    return 0;
}