백준 1474. 소수&팰린드롬

백준 1747. 소수&팰린드롬

소수이면서 팰린드롬인 수를 찾는 문제

이전에 푼거랑 약간 다름

1. 간단 설명

---

어떤 수 N이 주어지면

이 수 보다 같거나 큰 수들 중에서

소수이면서, 팰린드롬인 수 중 가장 작은 수를 찾아야한다

2. 예제

---

예를들어 10이 주어졌으면

10보다 같거나 큰 수들 중에서 소수이면서 팰린드롬인 수는 11이다

3. 알고리즘

---

1. N 입력받기
2. N이 소수이면서 팰린드롬인지 체크
3. 아니라면 1씩 올라가봄

이런식으로 완전탐색으로 찾아야한다

소수 체크와 팰린드롬 체크를 각 수마다 진행해야하므로

각 체크에 드는 시간이 길수록 시간초과가 나기 쉽다

이를 위해 에라토스테네스의 체와 정수를 이용한 팰린드롬 체크 사용

4. 소스코드

---

#include <iostream>

#define MAX 1003005
/*
N의 최대값 100,0000 보다 크고, 소수이면서 팰린드림인 수는
1003001이므로 여기까지만 살펴봄
*/

using namespace std;

bool isNotPrime[MAX]; // 에라토스테네스의 체 

// 팰린드롬인지 체크하는 함수. 숫자 뒤집기 사용
bool IsPalindrome(int num) {
	int rev = 0, original = num;
	// 숫자 뒤집기
	while (num > 0) { 
		rev = rev * 10 + num % 10; // 원본의 일의자리를 rev에 추가 후 10을 곱해줌
		num /= 10; 
	} 
	return original == rev; 
}

// 소수판별 함수. 시작할때 체를 초기화
void Init() {
	isNotPrime[1] = true; // 1은 소수가 아님
	for (int i = 4; i < MAX; i += 2) { // 2를 제외한 모든 짝수는 소수가 아님
		isNotPrime[i] = true;
	}
	// 홀수 소수 판별
	for (int i = 3; i * i < MAX; i += 2) {
		if (isNotPrime[i] == false) {
			for (int j = i * i; j < MAX; j += i) {
				isNotPrime[j] = true;
			}
		}
	}
}

int main() {
	int N;
	cin >> N;

	Init();

	for (int i = N; i <= MAX; i++) {
		if (IsPalindrome(i) && !isNotPrime[i]) {
			cout << i;
			break;
		}
	}

	return 0;
}