@[cy156](/user/1274005) 你自己算算时间复杂度,令 $n$ 为区间长度即 $b-a+1$,$O(n\sqrt{n})$ 的复杂度你想跑 $n=10^8$?这个运算量 $10^{12}$ 啊,不 TLE 有鬼了。
by FFTotoro @ 2024-03-23 15:43:45
@[zyc212303](/user/556366) 那请问这该怎么改啊!
by cy156 @ 2024-03-23 15:48:09
@[cy156](/user/1274005) 你自己去看题解。直接枚举肯定过不去的,需要一些优化。
by FFTotoro @ 2024-03-23 15:49:57
除数字11外,偶数个位数的数不存在回文质数,而且主函数循环还可以进一步优化。 @[cy156](/user/1274005)
by Yuufisher @ 2024-04-02 09:02:25
@[cy156](/user/1274005)
优化一下 `for` 循环
by lunjiahao @ 2024-04-10 19:10:10
@[cy156](/user/1274005)
只枚举奇数,因为质数中只有 `2` 是偶数
```cpp
if(a==2) cout<<a<<endl;
if(a%2==0) a++;
if(b>9999999) b=9999999;
for (int i = a;i <= b; i+=2)
```
by lunjiahao @ 2024-04-10 19:13:45
@[lunjiahao](/user/779970) 恕我直言,这样没有什么效果
by youcaiyoujuan @ 2024-04-10 22:40:17
利用回文数的性质减少枚举量,方法为构造回文数然后判断
```cpp
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
bool is_prime(int n){
for(int k = 2;k * k <= n;k++)
if(n % k == 0) return 0;
return 1;
}
int main()
{
int a,b,i,j;
cin >> a >> b;
for(i = a;i <= min(999999,b);i++)
{
if(is_prime(i)){//四位数及以下
string str = to_string(i);
for(j = 0;j <= (str.size() - 1) / 2;j++)
if(str[j] == str[str.size() - 1 - j]) continue;
else break;
if(j >= (str.size() - 1) / 2 + 1) cout << str << endl;
}
}
//七位数
for(int d3 = 1;d3 <= 9;d3++)
for(int d2 = 0;d2 <= 9;d2++)
for(int d1 = 0;d1 <= 9;d1++)
for(int d4 = 0;d4 <= 9;d4++)
{
int temp = d3 * 1000000 + d2 * 100000 + d1 * 10000 + d4 * 1000 + d1 * 100 + d2 * 10 + d3;
if(temp >= a&&temp <= b&&is_prime(temp)) cout << temp << endl;
}
//八位数
for(int d3 = 1;d3 <= 9;d3++)
for(int d2 = 0;d2 <= 9;d2++)
for(int d1 = 0;d1 <= 9;d1++)
for(int d4 = 0;d4 <= 9;d4++)
{
int temp = d3 * 10000000 + d2 * 1000000 + d1 * 100000 + d4 * 10000 + d4 * 1000 + d1 * 100 + d2 * 10 + d3;
if(temp >= a&&temp <= b&&is_prime(temp)) cout << temp << endl;
}
//九位数
for(int d3 = 1;d3 <= 9;d3++)
for(int d2 = 0;d2 <= 9;d2++)
for(int d1 = 0;d1 <= 9;d1++)
for(int d4 = 0;d4 <= 9;d4++)
for(int d5 = 0;d5 <= 9;d5++)
{
int temp = d3 * 100000000 + d2 * 10000000 + d1 * 1000000 + d4 * 100000 + d5 * 10000 + d4 * 1000 + d1 * 100 + d2 * 10 + d3;
if(temp >= a&&temp <= b&&is_prime(temp)) cout << temp << endl;
}
return 0;
}
```
by youcaiyoujuan @ 2024-04-10 22:44:06