AcWing 1356. 双指针
原题链接
简单
作者:
史一帆
,
2021-04-29 17:07:55
,
所有人可见
,
阅读 396
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7 + 10;
int p[N], cnt; // p[]:质数表
bool st[N];
bool check(int x)
{
string s = to_string(x);
for (int i = 0, j = s.size() - 1; i < j; i ++ , j -- )
if (s[i] != s[j])
return false;
return true;
}
void init(int n) // 筛质数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) p[cnt ++ ] = i;
for (int j = 0; p[j] <= n / i; j ++ )
{
st[p[j] * i] = true;
if (i % p[j] == 0) break; // 保证只被最小的质数筛掉
}
}
}
int main()
{
int a, b;
cin >> a >> b;
init(N);
for (int i = 0; i < cnt; i ++ )
{
if (p[i] >= a && p[i] <= b && check(p[i]))
cout << p[i] << endl;
}
return 0;
}