https://www.acmicpc.net/problem/1990
151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.
입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다.
첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다.
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <math.h>
#define lli long long int
#define MAX 10000001
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int a, b;
bool seive[MAX] = {
false,
};
bool ispalindrome(int n)
{
string s1 = to_string(n);
string s2 = s1;
reverse(s1.begin(), s1.end());
if (s1 == s2)
return true;
else
return false;
}
bool isPrime(int n)
{
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
fastio;
cin >> a >> b;
if (b > MAX - 1)
{
b = MAX - 1;
}
for (int i = 2; i < MAX; i++)
{
if (ispalindrome(i))
{
seive[i] = true;
}
}
for (int i = a; i <= b; i++)
{
if (seive[i])
{
if (isPrime(i))
{
printf("%d\n", i);
}
}
}
printf("-1");
return 0;
}