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

문제 링크

1747번: 소수&팰린드롬

문제 요약

N이 주어지면, N 이상의 팰린드롬인 소수 중에 가장 작은 수를 출력해야 한다.

접근 방법

전처리로 에라토스테네스의 체를 이용하여 200만 근처까지의 소수를 모두 구해 놨습니다. 그 다음에 구한 소수 목록에서, 입력 받은 N과 lower_bound를 통해서 인덱스를 구했습니다. 이제 해당 인덱스부터 팰린드롬인지 확인하면서 인덱스를 하나씩 이동시킵니다.

100만을 넣었을 때도 1003001이 정답으로 나오기 때문에, 200만 근처까지 소수 판정을 하면 매우 넉넉하게 돌아갑니다.

코드

#include <bits/stdc++.h>

using namespace std;

bool visited[2000000];
vector<int> prime;

void init(void)
{
	prime.reserve(2000000);

	for (int i = 2; i <= sqrt(2000000); i++)
		for (int j = i + i; j < 2000000; j += i)
			if (!visited[j])
				visited[j] = true;

	for (int i = 2; i < 2000000; i++)
		if (!visited[i])
			prime.push_back(i);
}

bool is_palindrome(int& num)
{
	string str = to_string(num);

	bool ret = true;
	for (int i = 0; i < str.size() / 2; i++)
	{
		if (str[i] != str[str.size() - 1 - i])
		{
			ret = false;
			break;
		}
	}

	return ret;
}

int main(void)
{
	int n;
	cin >> n;

	init();

	int pos = lower_bound(prime.begin(), prime.end(), n) - prime.begin();

	while (1)
	{
		if (is_palindrome(prime[pos]))
		{
			cout << prime[pos];
			return 0;
		}
		pos++;
	}
}