关于算法-数据结构:PAT甲级2020年春季考试-71-Prime-Day

7-1 Prime Day (20 分)

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

题目限度：

题目粗心：

给定数字串，其子串定义为终点从 0 到最初地位，起点为最初地位的数字串，判断每一个子串是否为素数，如果是输入该数和 Yes，否则输入该数和 No，如果所有的子串都是素数，最初输入All Prime!

算法思路：

应用字符串 s 承受输出的数字，只有 s 长度大于 0，就一直进行一下操作：

• 1、将 s 转化为数字 N，应用 isPrime 函数判断该数字是否为素数，如果是输入该数字和 Yes，否则输入该数字和No，并应用allPrime 记录不是所有子串都是素数。
• 2、令 s 为下一个子串s = s.substr(1)，转 1

  最初判断 allPrime 是否为true，如果是输入All Prime!

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>

using namespace std;

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

int main(){
    string s;
    cin>>s;
    bool allPrime = true;
    while (s.size()>0){int N = stoi(s);
        if(isPrime(N)){printf("%s Yes\n",s.c_str());
        } else {
            allPrime = false;
            printf("%s No\n",s.c_str());
        }
        s = s.substr(1);
    }
    if(allPrime) printf("All Prime!");
    return 0;
}