网站做的好赚钱吗,极速网站建设多少钱,折一把古风扇子,郑州做网站公司排题目描述
因为 151 151 151 既是一个质数又是一个回文数#xff08;从左到右和从右到左是看一样的#xff09;#xff0c;所以 151 151 151 是回文质数。
写一个程序来找出范围 [ a , b ] ( 5 ≤ a b ≤ 100 , 000 , 000 ) [a,b] (5 \le a b \le 100,000,000…题目描述
因为 151 151 151 既是一个质数又是一个回文数从左到右和从右到左是看一样的所以 151 151 151 是回文质数。
写一个程序来找出范围 [ a , b ] ( 5 ≤ a b ≤ 100 , 000 , 000 ) [a,b] (5 \le a b \le 100,000,000) [a,b](5≤ab≤100,000,000)一亿间的所有回文质数。
输入格式
第一行输入两个正整数 a a a 和 b b b。
输出格式
输出一个回文质数的列表一行一个。
1.题目分析
该题考查的是质数的判断回文数的判断以及对时间复杂度的控制。 质数的判断直接遍历取余是否为0即可 回文数的判断首先肯定是奇数数字的位数一定也是奇数 题目要求的一亿以内所以可以是1357位。 使用循环嵌套乘上数量级可以得到相应的回文数。
2.题目思路
首先写一个判断质数的函数为降低时间复杂度遍历1亿以内的数会出现超时 所以只对奇数奇数位数的数进行判断分别一个循环生成一位数的回文质数两个循环生成三位数的回文质数三个循环生成五位数的回文质数四个循环生成七位数到此已经达到了题目要求的一亿以内。 值得一提的是11偶数中的回文质数需要做一个特判。
3.代码演示
#include stdio.h
#include math.h//判断是否为质数
int isPrime(int n) {int flag 1;for (int i 2; i sqrt(n); i) {if (n % i 0) {flag 0;}}return flag;
}int main() {int d1, d2, d3, d4;int palindrome;int a, b;scanf(%d%d, a, b);//处理1位数 加上11//5到10for (d1 2; d1 11; d1) {palindrome d1;//(处理回文数...)if (isPrime(palindrome) 1 palindrome a palindrome b) {printf(%d\n, palindrome);}}//11到999//处理3位数for (d1 1; d1 9; d1 2) { // 只有奇数才会是素数for (d2 0; d2 9; d2) {palindrome d1 * 100 d2 * 10 d1;//(处理回文数...)if (isPrime(palindrome) 1 palindrome a palindrome b) {printf(%d\n, palindrome);}}}//1000到99999//处理5位数for (d1 1; d1 9; d1 2) { // 只有奇数才会是素数for (d2 0; d2 9; d2) {for (d3 0; d3 9; d3) {palindrome 10000 * d1 1000 * d2 100 * d3 10 * d2 d1;//(处理回文数...)if (isPrime(palindrome) 1 palindrome a palindrome b) {printf(%d\n, palindrome);}}}}// 100000到9999999//处理7位数 千万for (d1 1; d1 9; d1 2) { // 只有奇数才会是素数for (d2 0; d2 9; d2) {for (d3 0; d3 9; d3) {for (d4 0; d4 9; d4) {palindrome 1000000 * d1 100000 * d2 10000 * d3 1000 * d4 100 * d3 10 * d2 d1;//(处理回文数...)if (isPrime(palindrome) 1 palindrome a palindrome b) {printf(%d\n, palindrome);}}}}}return 0;
}
