题目描述 Problem Description
如果一个数从左边读和右边读都是同一个数，就称为回文数，例如686就是一个回文数。编程求10到1000内所有的既是回文数同时又是素数的自然数。
无。
输出描述 Output Description
若干个数，每行一个。
输入输出样例
输入样例1
输出样例1
正式开始题解！
这道题是个十分简单的枚举题，暴力判素也不会TLE。
先考虑普通做法。
想法是: 从10到1000，循环枚举每一个数，然后判断它是否是素数并且回文如果是，输出。
如何判素?
有一个最暴力的想法，从2一直枚举到x-1，判断这个数是否是x的因子。如果是，那么x不是质数。
如果枚举完了都没有return出去，那么可以确定x没有其他因子，是素数。
另外还有一个需要注意的点，当x小于2时，x也不为质数。
示范代码如下：
1
2
3
4
5
6
7
| bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i < x; i++)
if (x % i == 0)
return false;
return true;
}
|
时间复杂度是 的。
能不能更快？
答案是肯定的。素数是因子只有1和本身，如果x不是素数，则还有其他因子，其中的因子，假如为a，b.其中必有一个大于 ，一个小于 。所以必有一个小于或等于其平方根的因数，那么验证素数时就只需要枚举2到 就可以了。即一个合数一定含有小于它平方根的质因子。
示范代码如下：
1
2
3
4
5
6
7
| bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i < x; i++)
if (x % i == 0)
return false;
return true;
}
|
时间复杂度 ，大大滴优秀啊(赞赏)
如何判回文?
我们只需要将数字倒序，然后再看是否和原数相等就可以了。
如何把数字倒序?
最简单的想法是: 把数字转string然后再reverse。(接下来又是欢乐的代码环节了)
1
2
3
4
5
| int reverse(int x) {
string tostr = to_string(x);
reverse(tostr.begin(), tostr.end());
return stoi(tostr);
}
|
相信有了这些，你应该能A了这道题，祝你们成功
但还是在此贴出暴力A码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i * i < = x; i++)
if (x % i == 0)
return false;
return true;
}
int reverse(int x) {
string tostr = to_string(x);
reverse(tostr.begin(), tostr.end());
return stoi(tostr);
}
int main() {
for (int i = 10; i <= 1000; i++)
if (is_prime(i) && reverse(i) == i)
cout << i << endl;
return 0;
}
|
的复杂度用来AC这道题的确绰绰有余。但是我们还是要想: 还能更快吗?
没错，还能更快!
前置芝士 欧拉筛
欧拉筛(Euler sieve)，又名线性筛法，因其线性的复杂度而得名，用于筛出1~n之间的所有质数。
它在埃氏筛法上做了优化，把埃氏筛法 的近似 的复杂度彻底优化为 。原理是让每个数只被它的最小质因子筛一次，而不是像埃氏筛法一样用质数筛一个合数多次。
获取详细信息
在这里给出示例代码:
1
2
3
4
5
6
7
8
9
10
| void euler_sieve(int n) {
not_prime[0] = not_prime[1] = true;
for (int i = 2; i <= n; i++) {
if (!not_prime[i]) primes[primes_num++] = i;
for (int j = 0; j < primes_num && i * primes[j] <= n; j++) {
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
|
现在，我们就很自然地联想到: 这题可以用欧拉筛来做!
但是这有什么用呢? 不就是把 这一段优化掉了吗?
注意到不能让我们把复杂度化为 的罪魁祸首是: reverse函数!
所以现在重点放在reverse上。
reverse的优化
我们知道，传进reverse函数的值在[10, 1000]之间，只可能是[2, 4]位数。
所以我们可以特判x的位数，分别返回值。
1
2
3
4
5
| int reverse(int x) {
if (x < 100) return (x / 10) + (x % 10) * 10;
if (x < 1000) return (x / 100) + (x / 10 % 10) * 10 + (x % 10) * 100;
return 1;
}
|
接下来，让我们把所有元素结合到一起!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <iostream>
using namespace std;
bool not_prime[1001];
int primes[991];
int primes_num = 0;
void euler_sieve(int n) {
not_prime[0] = not_prime[1] = true;
for (int i = 2; i < n; i++) {
if (!not_prime[i]) primes[primes_num++] = i;
for (int j = 0; j < primes_num && i * primes[j] <= n; j++) {
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int reverse(int x) {
if (x < 100) return (x / 10) + (x % 10) * 10;
if (x < 1000) return (x / 100) + (x / 10 % 10) * 10 + (x % 10) * 100;
return 1;
}
int main() {
euler_sieve(1000);
for (int i = 0; i < primes_num; i++)
if (primes[i] > 9 && primes[i] == reverse(primes[i]))
cout << primes[i] << '\n';
return 0;
}
|
