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

코드

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

using namespace std;

// N이 백만인 경우, 1003001이 나올 수 있음
// N과 2N 사이에는 소수가 항상 존재한다는 성질을 이용
int n, prime[2000003],res;

bool isPell(int x) {
	string s = to_string(x);
	int st = 0;
	int e = s.length() - 1;
	while (st <= e) {
		if (s[st] != s[e]) return false; // 앞과 뒤가 다르면 펠린드롬 X
		st++;
		e--;
	}
	return true;
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}


int main() {
	FASTIO();
	cin >> n;
	fill(prime, prime + 2000003, 1);
	prime[0] = 0;
	prime[1] = 0;
	// 에라토스테네스의 체
	for (int i = 2; i * i < 2000003; i++) {
		int j = 2;
		while (i * j < 2000003) {
			prime[i * j] = 0;
			j++;
		}
	}
	for (int i = n; i < 2000003; i++) {
		if (prime[i] && isPell(i)) {
			res = i;
			break;
		}
	}
	cout << res << '\n';
	return 0;
}

풀이

에라토스테네스의 체를 이용해서 소수를 찾아주었다. 그리고 펠린드롬을 확인하는 함수를 이용했다. 앞과 뒤를 차례차례확인해 만약 다르면 false, 끝까지 같으면 true를 반환하여 그 값을 출력하게 했다. 한 가지 안 사실은, N과 2N 사이에는 소수가 항상 존재한다는 사실이다. 정수론 풀 때 도움이 될 거 같다.