[BOJ/C++] 1747 소수 & 팰린드롬

에라토스테네스의 체와 회문을 이용하여 문제를 해결할 수 있습니다.

먼저 에라토스테네스의 체를 이용하여 소수를 구해준 뒤 제일 먼저 찾는 소수이자 회문인 수를 찾으면 됩니다.

// boj s1 1747
// 소수 & 팰린드롬
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;

static bool v[10000001];

int main(void)
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int N;
    cin >> N;

    v[0]=true;
    v[1]=true;

    for(int i=2; i<=10000; i++)
    {
        for(int j=2; i*j<=10000000; j++)
        {
            // 백만보다 큰 첫번째 소수이면서 팰린드롬 수 찾기
            v[i*j]=true;
        }
    }

    for(int i=N; i<=10000000; i++)
    {
        if(!v[i])
        {
            string temp=to_string(i);
            reverse(temp.begin(), temp.end());
            if(stoi(temp)==i)
            {
                cout << i;
                return 0;
            }
        }
    }


    return 0;
}