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

안유태·2023년 9월 10일
0

알고리즘

목록 보기
138/239

1747번: 소수&팰린드롬

에라토스테네스의 체를 이용하여 푸는 문제이다. 먼저 에라토스테네스의 체를 이용하여 소수를 구해주었다. 그 후 반복문을 돌면서 소수인 수 중에서 팰린드롬에 해당하는지 확인을 한 후 해당하면 저장을 한 후 출력해주었다. 로직 자체는 어렵지 않은 문제였다. 범위를 처음에는 2,000,000으로 두었는데 이때 범위 문제로 계속해서 틀렸었고 범위를 1,003,002로 두니 통과하였다. 범위 문제로도 틀릴 수 있다는 것을 알아두자.



#include <iostream>
#include <string>

#define SIZE 1003002

using namespace std;

int N;
bool p[SIZE];

void prime() {
	for (int i = 2; i <= SIZE; i++) {
		if (p[i]) continue;

		for (int j = i + i; j <= SIZE; j += i) {
			p[j] = true;
		}
	}
}

bool check(int n) {
	string s = to_string(n);
	int start = 0;
	int end = s.size() - 1;

	while (start <= end) {
		if (s[start] == s[end]) {
			start++;
			end--;
		}
		else {
			return false;
		}
	}

	return true;
}

void solution() {
	int result = 0;

	for (int i = N; i <= SIZE; i++) {
		if (p[i]) continue;

		if (check(i)) {
			result = i;
			break;
		}
	}

	result = result == 1 ? 2 : result;
	cout << result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	prime();
	solution();
	
	return 0;
}
profile
공부하는 개발자

0개의 댓글