백준 알고리즘 1990번 : 소수인팰린드롬

링크

https://www.acmicpc.net/problem/1990

문제

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

입력

입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다.

출력

첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다.

예제 입력 및 출력

풀이법

1. 제한 시간이 1초이므로 에라토스테네스의 체와 팰린드롬 검사를 통해서 구간 안에 해당하는 수들을 전부 구했지만 시간초과 및 메모리초과...
   그래서 방법을 바꿨더니 정답 처리가 되었다.

• 방법 2

1. 펠린드롬 숫자를 먼저 구한다.
2. 구해진 모든 팰린드롬 숫자를 대상으로 소수 판정(2부터 x까지 나누었을 때 나누어 떨어지는게 하나라도 있으면 소수가 아니고 그렇지 않으면 소수!)을 실시한다.
3. 정답을 출력한다.

풀이 코드(C++)

#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;
}