BOJ - 1747번 소수&팰린드롬(C++)

문제 출처: https://www.acmicpc.net/problem/1747

문제 난이도

Gold 5

문제 접근법

문제 나타낸대로 구현하면 된다. 하지만 주의할 점은 바로 범위 소수가 1000,000까지인데 이게 범위가 여기까지인게 아니라 N이 백만일때 나타날 소수범위까지를 고려해야한다.
가장 작은 소수이자 팰린드롬은 1003001이다.

통과 코드

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

using namespace std;

bool isPrime[1003002];

void estro() {
	for (int i = 2; i <= 1003002; i++) {
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i <= 1003002; i++) {
		for (int j = 2; j*j <= i; j++) {
			if (i%j == 0) {
				isPrime[i] = false;
				break;
			}
		}
	}
}

bool isSame(int N) {
	string s = to_string(N);
	int size = s.size();
	for (int i = 0, j = size - 1; i < size, j >= 0; i++, j--) {
		if (s[i] != s[j]) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	estro();
	for (int i = N; i <= 1003002; i++) {
		if (isPrime[i] && isSame(i)) {
			cout << i << "\n";
			break;
		}
	}
	return 0;
}