[C++][백준] 소수&팰린드롬(1747)

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

풀이

어떤 수가 소수인지 아닌지 판별하는 과정을 수차례 반복해야 할때 에라토스테네스의 체를 이용할 수 있습니다.

isPrime[i]가 true라면 어떤 수 i가 소수라는 의미입니다.1은 소수가 아니기 때문에 isPrime[1] = false로 설정하였습니다.

 

에라토스테네스의 체는 아래와 같이 구현할 수 있습니다.

void findPrime() {
	isPrime[1] = false;
	for (int i = 2; i <= 10000000; i++) {
		if (isPrime[i] == true) {
			for (int j = 2; i * j <= 10000000; j++) {
				isPrime[i * j] = false;
			}
		}
	}
}

 

 

아래는 어떤 수가 팰린드롬인지 판별하는 함수입니다.

먼저 정수를 string으로 변환하기 위해

 

#include <iostream>을 선언해주고 to_string() 함수를 사용하였습니다.

bool isPalindrome(int n) {
	string s = to_string(n);

	int length = s.size();
	int mid = length / 2;
	for (int i = 0; i < mid; i++) {
		if (s[i] != s[length - i - 1]) return false;
	}
	return true;
}

 

전체 코드는 아래와 같습니다. 

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

long long N;
bool isPrime[10000100];

void init() {
	for (int i = 1; i <= 10000000; i++) {
		isPrime[i] = true;
	}
}

void findPrime() {
	isPrime[1] = false;
	for (int i = 2; i <= 10000000; i++) {
		if (isPrime[i] == true) {
			for (int j = 2; i * j <= 10000000; j++) {
				isPrime[i * j] = false;
			}
		}
	}
}

bool isPalindrome(int n) {
	string s = to_string(n);

	int length = s.size();
	int mid = length / 2;
	for (int i = 0; i < mid; i++) {
		if (s[i] != s[length - i - 1]) return false;
	}
	return true;
}

int main() {
	init();
	findPrime();

	cin >> N;

	for (int i = N; ; i++) {
		if (isPrime[i]) {
			if (isPalindrome(i)) {
				cout << i;
				break;
			}
		}
	}

	return 0;
}