[백준 - C++] 1747번: 소수&팰린드롬

소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하는 것이 이번 문제 되시겠다.

그럼 바로 코드로 가보겠습니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool sosu(int num) {
    if (num < 2) 
    	return false;
    int a = static_cast<int>(sqrt(num));
    for (int i = 2; i <= a; i++) 
    	if (num % i == 0) 
    		return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    int i = n;
    while(true)
    {
        if (sosu(i))
        {
            string str_rev = to_string(i);
            reverse(str_rev.begin(), str_rev.end());
            if(str_rev == to_string(i))
            {
                printf("%d\n", i);
                break;
            }
        }
        i++;
    }
    
    return 0;
}

우선 소수를 판별하는 함수를 만들었다. 소수일 경우 true를, 아닐 경우엔 false를 반환한다. 시간을 최대한 단축하기 위해서 2부터 n-1까지 for문을 돌리는게 아니라 제곱근을 한 것까지 돌리는 것으로 제작했다.

 

팰린드롬은 앞으로 읽어도, 뒤로 읽어도 똑같은 우영우, 기러기, 역삼역...이런 건데 숫자로 보면 101, 343 이런 숫자다. 이건 숫자를 string으로 바꿔서 reverse한 것과 비교했을 때 같은지 판별만 하면 되기 때문에 아주 쉽다. 이래서 C++ 쓰는건가? 

아무튼 그래서 to_string함수로 string으로 형변환하고, reverse함수로 순서를 바꿔주면 된다. 그래서 이 reversed된 것과 기존 to_string으로 변환된 것이 같으면 브레이크를 걸어서 출력한다.

그게 아니면 계속 while문으로 돌리면서 하나씩 숫자를 키워나간다.

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

1747번: 소수&팰린드롬