백준 1747번 C++

백준 1747번 소수&팰린드롬

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

정답 코드

#include <iostream>
#include <math.h>
#define MAX 8000001             
int prime[MAX] = { 1, };
using namespace std;
int reverse(int n) {
	int r = 0;
	while (n != 0) {
		r *= 10;
		r += n % 10;
		n /= 10;
	}
	return r;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (int i = 2; i <= sqrt(MAX); i++) {
		if (prime[i] != 0)
			continue;
		for (int j = i * i; j <= MAX; j += i) {
			prime[j] = 1;
		}
	}

	int a;
	cin >> a;
	if (a == 1) {
		cout << 2;
		return 0;
	}
	int index = 0, flag = 0;
	for (int x = a; x < MAX; x++) {
		if (flag == 1)
			break;
		if (prime[x] == 0) {
			index = x;
			if (reverse(x) == index) {
				cout << index;
				return 0;
			}
		}
	}
}

문제 풀이

주어진 범위 안에서 소수와 펠린드롬을 동시에 만족하는 가장 작은 수를 찾는 문제입니다. 소수는 에라토스테네스의 체를 이용해서 구한 뒤 펠린드롬은 역수를 출력해주는 함수를 만들었습니다. 역수는 n의 몫을 계속해서 더해주면서 r에 10을 계속 곱해줍니다. 그리고 n은 0이 될 때까지 계속 10을 나누어 줍니다.