题目描述因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。
写一个程序来找出范围 [a,b] (5 le a < b le 100,000,000)[a,b](5≤a
当然呢我们直接暴力会时间超限
先给出时间超限的代码,当然对于小数据还是可以通过的嘿嘿。
#includeusing namespace std; bool hw(int n) { int t = n; int sum = 0; while (t) { sum = sum * 10 + t % 10; t /= 10; } if (sum == n) return true; else return false; } bool zs(int n) { for (int i = 2; i < sqrt(n); i++) { if (n % i == 0) return false; } return true; } int main() { int x, y; cin >> x >> y; for (int i = x; i <= y; i++) { if (zs(i) && hw(i)) cout << i << 'n'; } return 0; }
接下来给出完全ac的代码
接下来完成第一个任务判断回文数
bool hw(int n) { int t = n; int sum = 0; while (t) { sum = sum * 10 + t % 10; t /= 10; } if (sum == n) return true; else return false; }
懂得都懂,不多bb;
然后就是判断质数呢,还有怎样防止时间超限呢??
首先正整数除偶数2以外都不是质数,时间大约减少一半,其次通过百度可以知道位数是偶数位的一定不是回文质数除了11.。。。。。。。
bool zs(int n)//判断质数 { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }
bool ws(int k) //没有偶数位数的回文质数 { if (k >= 10 && k < 100 && k != 11 || k >= 1000 && k < 10000)return false; if (k >= 100000 && k < 1000000 || k >= 10000000 && k < 100000000)return false; return true; }
这样就能过八个测试点了但是最后一个测试点是真的狗啊一直TEL
int main() { int x, y; scanf("%d%d", &x, &y); if (x == 2) printf("2n"); if (x % 2 == 0) x++; y = min(y, 9999999); for (int i = x; i <= y; i+=2) { if (hw(i) && ws(i) && zs(i)) printf("%dn", i); } return 0; }
如果不加min这句判断是不会过最后一个测试点的。。。。。。。
这样的话就万无一失了哈哈哈哈
目录
题目描述
题目描述
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)