[백준] 1990 - 소수인팰린드롬

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

1990번: 소수인팰린드롬

 

두 수가 주어지고, 그 두 수를 포함하는 사이의 수 중에서 소수이면서 팰린드롬을 찾는 문제이다.

 

두 수의 차의 최대는 대략 1억이기 때문에, 모든 숫자를 찾으며 문제를 풀 수 없다.

 

그렇다면 먼저 팰린드롬이라는 것을 찾아보자.

팰린드롬은 앞으로 읽어도, 뒤로 읽어도 같은 수이다.

 

그래서 자릿수가 짝수인 팰린드롬은, 홀수 자리의 숫자의 합과 짝수 자리 숫자의 합의 차가 항상 0이다.

그리고 이러한 수가 바로 11의 배수이다.

따라서 8자리 수의 팰린드롬은 모두 11의 배수, 즉 소수가 아니라는 것이다.

 

결론적으로 b의 범위가 9999999로 변경되었다.

다음으론 소수 판정 알고리즘을 통해서 소수를 구하면 된다.

 

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

bool isPrime(int a) {
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0) return false;
	}

	return true;
}

bool palindrome[10000001];

void isPalindrome(int a, int b) {
	for (int i = a; i <= b; i++) {
		string s1 = to_string(i);
		string s2 = s1;
		reverse(s2.begin(), s2.end());
		if (s1 == s2) palindrome[i] = 1;
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cout.tie(0);

	int a, b;
	cin >> a >> b;
	isPalindrome(a, min(10000000, b));
	for (int i = a; i <= min(10000000, b); i++) {
		if (palindrome[i])
			if (isPrime(i)) {
				cout << i << '\n';
			}
	}
	cout << -1;
}