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 Yes0190523 Yes190523 Yes90523 Yes0523 Yes523 Yes23 Yes3 YesAll Prime!
Sample Input 2:
20191231
Sample Output 2:
20191231 Yes0191231 Yes191231 Yes91231 No1231 Yes231 No31 Yes1 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;}