BOJ - 1747 - 소수&팰린드롬

ggh·2022년 5월 11일

boj bruteforce cpp ps

백준

목록 보기

30/112

BOJ - 1747 - 소수&팰린드롬

문제

1747번: 소수&팰린드롬

문제 개념

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

구현

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    int num;
    int answer;
    cin >> num;
    vector<bool> arr(10000001, 0);
    arr[1] = true;
    for(int i=2; i <= sqrt(10000000); i++)
    {
        if(!arr[i])
            for(int j=i+i; j <= 10000000; j+=i)
                arr[j] = true;
    } 
    for(int i=0; i < 10000001; i++)
    {
        if(!arr[i] && i >= num)// 소수 이면서
        {   // 문자열로 변환 후 revese시에도 같은수면 
            string temp = to_string(i);
            reverse(temp.begin(), temp.end());
            if(temp == to_string(i))
            {
                answer = i;
                break;
            }
        }
    }
    cout << answer << endl;
    return 0;
}