[알고리즘] 백준 1990번: 소수인팰린드롬 (C++), 이런 문제는 어떡하지

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

1990번: 소수인팰린드롬

---

솔루션

1) 에라토스테네스의 체를 통해 입력받은 b보다 작거나 같은 소수들을 구한다.

2) a와 b 사이의 범위를 만족시키기 위해 이분 탐색을 통해 시작과 끝 범위를 찾는다.

3) bool 타입의 팰린드롬 판별 함수를 통해 소수 중에 팰린드롬을 찾는다.

4) -1 출력, 종료

>> 다음 솔루션은 메모리 초과 발생

>> 게시판 질문 글에서 10,000,000을 넘어가는 팰린드롬인 소수는 없다고 한다.

(https://www.acmicpc.net/board/view/1961)

 

그래서 소수를 구할 때 b가 10,000,000을 넘는 경우 10,000,000을 넘어가지 않게 조건을 걸어주었다.

if (b >= 10000000) {
	b = 10000000;
}

그런데 저런 경우로 메모리 초과가 되는 경우는 어떻게 해야 할까?

10,000,000을 넘어가는 소수인 팰린드롬이 없다는 것을 알아내는 것도 능력 중 일부인가?

혹은 팰린드롬 판별 함수를 더 작게 줄일 수 있는 걸까

---

[AC 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <string>
using namespace std;

vector<int> num;
vector<int> prime;
int a, b;

void primeSave() {
	if (b >= 10000000) {
		b = 10000000;
	}

	for (int i = 0; i <= b; i++) {
		num.push_back(i);
	}

	for (int i = 2; i <= sqrt(b); i++) {
		if (num[i] != 0) {
			for (int j = i + i; j <= b; j += i) {
				num[j] = 0;
			}
		}
	}

	for (int i = 2; i < num.size(); i++) {
		if (num[i] != 0) {
			prime.push_back(num[i]);
		}
	}
}

bool isRight(string temp) {
	if (temp.size() == 1) {
		return 1;
	}

	stack<char> s;
	if (temp.size() % 2 == 0) {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = temp.size() / 2; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
	else {
		for (int i = 0; i < (temp.size() / 2); i++) {
			s.push(temp[i]);
		}
		for (int i = (temp.size() / 2) + 1; i < temp.size(); i++) {
			if (s.top() == temp[i]) {
				s.pop();
			}
			else {
				return 0;
			}
		}
		return 1;
	}
}

int main() {
	cin >> a >> b;
	primeSave();

	int start = lower_bound(prime.begin(), prime.end(), a) - prime.begin();
	int end = upper_bound(prime.begin(), prime.end(), b) - prime.begin();

	for (int i = start; i < end; i++) {
		if (isRight(to_string(prime[i]))) {
			cout << prime[i] << '\n';
		}
	}
	cout << -1;
	return 0;
}