[C++][백준] 1990 소수인팰린드롬

이번 문제는 소수판정과 팰린드롬 판정을 하는 문제이다.

문제

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

 

입력

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

 

출력

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

 

아이디어

 

소수를 판정하기 위해서는 에라토스테네스의 체 방법을 사용하는 것이 편하다.
에라토스테네스의 체란, 소수를 제외한 소수의 배수는 모두 지워나가며 소수만을 남기는 방법이다.

 

    ll A = [100000000];
    for(int i=2; i< sqrt(N); i++) // 에라토스테네스 체
        if(!A[i])
            for(int j=i*2; j<=N; j+=i)
                if(!A[j])
                    A[j] = 1;

 

 

이런식으로 작성해주었다.

 

 

팰린드롬수는 1001처럼 뒤로 읽어도 원래 수랑 같은 수를 말한다.

bool is_palindrome(int num) {
    int num_original = num;
    int num_rev = 0;
    while (num > 0) {
        num_rev = num_rev*10 + num % 10;
        num /= 10;
    }

    return num_original == num_rev;
}

 

이런식으로 해당 숫자를 뒤집어서 원본과 비교해주는 방법을 사용했다.

그래서 소수 리스트에 들어가면서 팰린드롬수인 숫자를 출력해주는 조건문을 넣어서 출력해보려고 했는데,

 

메모리 초과가 나와버렸다.
아마 소수 판정을 위한 배열의 길이가 너무 길어서 그런것 같다.

 

 

그래서 약간 편법을 사용하기로 했다.

#include <bits/stdc++.h>
using namespace std;
int arr[] = {5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373,
383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311,
11411,12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741,
15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 
....
9932399, 9935399, 9938399, 9957599, 9965699, 9978799,9980899,
9981899, 9989899};
int a,b;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b;
    for(int i:arr)
    {
        if(i>=a && i<=b)
            cout << i<< '\n';
        if(i>b)
            break;
        if(i>100000000)
            break;
    }
    cout << -1;
    return 0;
}

 

 

소수와 팰린드롬수의 공통영역에 있는 수는 전부 뽑아낼 수는 있기 때문에 전부 출력해보았다.
대략 800개 좀 안되게 나와서 이 숫자들을 모두 배열에 넣고

입력받을 a,b범위 사이에 있는 숫자들만 출력하도록 코드를 작성하였다.