BOJ : 1747 소수&팰린드롬

---

[BOJ 1747(G5)리뷰]

N을 입력받아 N보다 크거나 같은 소수 중 팰린드롬인 수를 출력하면 된다.

예를들어 31을 입력받았다면, 31보다 큰 소수중 팰린드롬인 수 101을 출력하면 된다.

이 문제를 풀기위해 크게 두가지 과정을 거쳤다.
1.소수 판별 (에라토스테네스의 체)
2.팰린드롬 판별

처음에 N의 범위가 최대 100만이라 100만까지의 수만 소수판별을 했는데 만약 100만이 입력되었을 경우 100만보다 크거나 같은 소수를 출력해야하므로, 100만보다 크거나 같은 소수 중 팰린드롬 수인 1003001까지 소수판별을 해야 한다.

1003001까지의 소수판별을 한 후에 소수들을 하나의 벡터에 넣고, 입력받은 N의 위치를 lower_bound로 구했다.
이러면 N에서 가장 가까운 소수의 위치를 알 수 있다. 이 위치부터 시작하여 저장된 소수의 마지막까지 반복문을 돌며 팰린드롬인지 아닌지 확인 해 주면 된다. 확인할땐 string으로 변환하여 확인했다.

/*
	21.01.29
	BOJ : 1747 촌수계산 (https://www.acmicpc.net/problem/1747)
	소수판별
*/
#include <bits/stdc++.h>
using namespace std;

bool check[1003002];
vector <int> prime;

bool isP(string s) {
	int len = s.size();
	for (int i = 0; i < len / 2; i++) {
		if (s[i] != s[len - 1 - i]) {
			return false;
		}
	}

	return true;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    
	for (int i = 2; i <= 1003001; i++) {
		if (check[i]) continue;

		for (int j = 2 * i; j <= 1003001; j += i) {
			check[j] = 1;
		}
	}

	for (int i = 2; i <= 1003001; i++) {
		if (!check[i])
			prime.push_back(i);
	}

	int n;
	cin >> n;
	
	auto s = lower_bound(prime.begin(), prime.end(),n);
	
	for (; s != prime.end(); s++) {
		if (isP(to_string(*s))) {
			cout << *s;
			break;
		}
	}
	
	return 0;
}