[BaekJoon/백준] 1747번 - 소수 & 펠린드롬

 

#include <iostream>
#include <algorithm>
#include <string>

int N;
bool check[1040000] = {true, true};

using namespace std;

int main() {
    
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    for(int i = 2; i * i <= 1004000; i++) {
        
        if(check[i]) continue; // 이미 약수의 배수로 체크되었을거임.
        
        for(int j = i + i; j <= 1040000; j+=i)
            check[j] = true;
        }

    
    cin >> N;
    string s, o;
    
    
    for(int i = N; i <= 1040000; i++) {
        
        
        if(!check[i]) {
            
            o = s = to_string(i);
            reverse(s.begin(), s.end());
            
            if(o == s) {
                cout << i << "\n";
                break;
            }
            
            
        }
        
    }
    
}

 

이 문제에서 조심해야 할 사항은 두가지다.

 

1. N은 100만 이하이지만, 출력에서 나올 수는 100만보다 클 수있다. 따라서 100만보다 큰 수 중에 가장 작은 펠린드롬 수가 있는 곳 까지 범위를 포함시켜야한다. ( 1003001 이 되겠음 )

 

2. 입력으로 1이 들어왔을 때 2가 나와야 한다. 1은 소수가 아니기 때문.