解题思路:
从简单的来看,比如只有一位,那么必然只有 2,3,5,7
再看两位,由题目要求,该两位数必为质数,且丢弃个位后,仍为质数。
那么反过来看,从一位到两位,有什么规律呢?
核心:以一位 5 为例,欲扩展到两位,最多只要判断 51,53,57,59 即可,也就是 (5*10) + 1 / +3 / +7 / +9
【个位为0,2,4,6,8一定不为质数,5也排除在外
再继续看,以53为例,欲扩展至三位,最多只要判断 531,533,537,539 即可 也就是 (53*10) + 1 / +3 / +7 / +9
所以规律已经显而易见了
(如果采用暴力算法,例如N=3,去遍历100~999再判断的话,必然超时,再怎么优化细节也不可行(主要是N=8太久了)
注意事项:
判断质数函数 用的不是最优算法,有兴趣的同学再去研究一下吧
参考代码:
#include<bits/stdc++.h> using namespace std; bool IsPrime(int num) { if (num <= 3) return num > 1; int s = sqrt(num); for (int i = 2; i <= s; ++i) { if (num % i == 0) return false; } return true; } int main() { int n; while (cin >> n) { // int型链表 list<int> li; // 迭代器 list<int>::iterator iter; int i, j, tmp; // 记录当前n所对应的特殊质数的个数,比如n=1时,count=4 int count = 0; // 初始化为 2 3 5 7 li.push_back(2); li.push_back(3); li.push_back(5); li.push_back(7); // 从n=1开始,扩展到题目要求的n for (i = 1; i < n; ++i) { // 更新count count = li.size(); // 从list第一个数开始处理 iter = li.begin(); // 一共处理count个数 while (count != 0) { // 优化效率,防止多次运算 tmp = (*iter) * 10; // 取完数后,指针指向下一个待处理的数 iter++; // 删除已记录在tmp的那个数 li.pop_front(); // 更新count count--; // 对应的 +1 +3 +7 +9,想写循环的话:tmp += 2,但是这样写更直观 if (IsPrime(tmp + 1)) { li.push_back(tmp + 1); } if (IsPrime(tmp + 3)) { li.push_back(tmp + 3); } if (IsPrime(tmp + 7)) { li.push_back(tmp + 7); } if (IsPrime(tmp + 9)) { li.push_back(tmp + 9); } } } // 输出即可 for (iter = li.begin(); iter != li.end(); ++iter) { cout << (*iter) << endl; } } return 0; }
解题思路:
嫌上面麻烦的同学,这里有一份更直接的AC代码
注意事项:
定向输出!
参考代码:
#include<bits/stdc++.h> using namespace std; void outputArr(int A[], int size) { for (int i = 0; i < size; ++i) { cout << A[i] << endl; } } int main() { int n; while (cin >> n) { int N1[] = { 2,3,5,7 }; int N2[] = { 23,29,31,37,53,59,71,73,79 }; int N3[] = { 233,239,293,311,313,317,373,379,593,599,719,733,739,797 }; int N4[] = { 2333,2339,2393,2399,2939,3119,3137,3733,3739,3793,3797,5939,7193,7331,7333,7393 }; int N5[] = { 23333,23339,23399,23993,29399,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939 }; int N6[] = { 233993,239933,293999,373379,373393,593933,593993,719333,739391,739393,739397,739399 }; int N7[] = { 2339933,2399333,2939999,3733799,5939333,7393913,7393931,7393933 }; int N8[] = { 23399339,29399999,37337999,59393339,73939133 }; switch (n) { case 1: outputArr(N1, 4); break; case 2: outputArr(N2, 9); break; case 3: outputArr(N3, 14); break; case 4: outputArr(N4, 16); break; case 5: outputArr(N5, 15); break; case 6: outputArr(N6, 12); break; case 7: outputArr(N7, 8); break; case 8: outputArr(N8, 5); break; default: break; } } return 0; }
0.0分
9 人评分
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:385 |
校门外的树 (C语言代码)浏览:955 |
简单的a+b (C语言代码)浏览:334 |
母牛的故事 (C语言代码)浏览:1426 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:560 |
C二级辅导-计负均正 (C语言代码)浏览:480 |
时间转换 (C语言代码)浏览:623 |
A+B for Input-Output Practice (I) (C语言代码)浏览:426 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:503 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2131 |