1168 Prime Day – PAT甲级真题

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

题目大意：2019年5月23日是个“全素日”，即不仅20190523本身是个素数，它的任何以末尾数字3结尾的子串都是素数。本题就请你写个程序判断一个给定日期是否是“全素日”。输入按照yyyymmdd的格式给出一个日期。题目保证日期在0001年1月1日到9999年12月31日之间。从原始日期开始，按照子串长度递减的顺序，每行首先输出一个子串和一个空格，然后输出Yes，如果该子串对应的数字是一个素数，否则输出No。如果这个日期是一个全素日，则在最后一行输出All Prime!。

分析：使用num储存合数的个数，如果最后num为0，则表示要输出”All Prime!”。使用string s存储输入的数字。可以使用while循环，每次查询当前数值是不是素数，然后使用erase()函数删除第一个数字，如此循环到s长度为0。可以直接使用函数stoi()，将string转化成int类型。每次我们判断当前的数是不是素数，并直接输出。

#include <iostream>
#include <cmath>
using namespace std;
int num;
string s;
int is_prime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return 0;
    return 1;
}
int main(){
    cin >> s;
    num = s.size();
    while (s.size()) {
        cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';
        if (is_prime(stoi(s))) --num;
        s.erase(s.begin());
    }
    if (num == 0) cout << "All Prime!";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int num;

string s;

int is_prime(int x) {

if (x < 2) return 0;

for (int i = 2; i <= sqrt(x); i++)

if (x % i == 0) return 0;

return 1;

}

int main(){

cin >> s;

num = s.size();

while (s.size()) {

cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';

if (is_prime(stoi(s))) --num;

s.erase(s.begin());

}

if (num == 0) cout << "All Prime!";

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版