BOJ 1747 소수&팰린드롬

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

팰린드롬 수는 어떤 수를 반대로 뒤집고 그 수가 같다면 팰린드롬 수이다.

에라토스테네스의 채를 사용해서 소수를 판단해주고 문자열을 사용해서 뒤집고 체크해주면 되는 쉬운 문제였다.

 

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

vector<bool> sieve(1100001);

void era(int n) {
	fill(sieve.begin(), sieve.end(), true);
	sieve[0] = sieve[1] = false;
	for (int i = 2; i * i <= 1100000; i++) {
		if (sieve[i]) {
			for (int j = i * 2; j <= 1100000; j += i) sieve[j] = false;
		}
	}
}

bool palindrome(string a) {
	string b(a);
	reverse(b.begin(), b.end());
	if (a == b) return true;
	return false;
}

int main() {
	int n;
	cin >> n;
	era(n);
	for (int i = n; i < 1100001; i++) {
		if (sieve[i] && palindrome(to_string(i))) {
			cout << i << endl; break;
		}
	}
	return 0;
}

주의해야 될 점은 N이 백만까지인데 뒤집은 숫자가 백만보다 클 수 있으므로 여유롭게 110만으로 설정해뒀다.