[C++] 백준 1747번 - 소수&팰린드롬

팰린드롬 문제이다

이 팰린드롬 문제때문에 전공 하나 B0받은 것을 생각하면 치가 떨리는 알고리즘(?)이다.

각설하고,

에라토스테네스의 체로 소수인 숫자들을 vector에 미리 넣어놓고

vector의 숫자보다 같거나 큰 소수들을 탐색하면서

팰린드롬인지 확인해주면 된다

숫자가 커서 vector로 문제를 풀 때 메모리가 많이 소모될 줄 알았는데

다행히 6720kb밖에 소모되지 않았다.

 

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

#define MAX 1003001
int arr[1003002];
vector<int> v;
//에라토스테네스의 체

void prime() {
	for (int i = 2; i <= MAX; i++) {
		arr[i] = i;
	}

	for (int i = 2; i <= MAX; i++) {
		if (arr[i] == 0)
			continue;
		v.push_back(arr[i]);
		for (int j = 2 * i; j <= MAX; j += i)
			arr[j] = 0;
	}
}

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

	bool check = false;
	prime();

	for (int i = 0; i < v.size(); i++) {
		if (v[i] >= n) {
			check = true;
			string s = to_string(v[i]);
			for (int j = 0; j < s.length() / 2; j++) {
				if (s[j] != s[s.length() - j - 1]) {
					check = false;
					break;
				}

			}
			if (check) {
				cout << v[i] << "\n";
				return 0;
			}
		}
	}

	return 0;
}