백준 1747 c++ "소수&팰린드롬" -PlusUltraCode-

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

 

[필자 사고]

처음 에스토라 채를 이용할 때 최대를 10^7 했더니 런타임 속도가 많이 느렸다.

그래서200만 으로 바꿔서 진행해서 풀렸다.

 

팰린드롬 구하는 방법은 인덱스를 이용하여 처음과 끝을 비교하면서 했다.

문제에서 제한이 없어 쉽게 풀 수 있었다. 

[코드 해설]

1. EesTora_Chae()

• 기능: 소수를 판별하기 위한 에라토스테네스의 체 알고리즘을 사용하여 isPrime 벡터를 초기화합니다.
• 상세 동작:
  • isPrime 벡터를 MAX 크기만큼 true로 초기화한 뒤, 0과 1은 소수가 아니므로 false로 지정.
  • 2부터 √MAX까지 반복하면서, 현재 수가 소수이면 그 수의 배수들을 모두 false로 설정합니다.
  • 이렇게 하면 isPrime[i] == true인 i만 소수입니다.

---

2. isPelindlin(int num)

• 기능: 주어진 정수 num이 팰린드롬 수(앞뒤가 같은 수) 인지 확인합니다.
• 상세 동작:
  • 숫자의 각 자릿수를 벡터에 저장한 뒤, 앞뒤에서 서로 비교하며 팰린드롬인지 확인합니다.
  • 예: 131 → [1, 3, 1] → 앞뒤 일치 → true

---

3. Input()

• 기능: 사용자로부터 입력값 N을 받고, 에라토스테네스의 체를 초기화하는 EesTora_Chae()를 호출합니다.

---

4. Game_Start()

• 기능: N 이상 MAX 미만의 모든 수에 대해, 소수이면서 팰린드롬인 수를 찾습니다.
• 상세 동작:
  • N부터 시작하여 isPrime[i]가 true인 경우, 해당 숫자가 팰린드롬인지 isPelindlin()으로 확인.
  • 둘 다 만족하면 그 수를 출력하고 프로그램을 종료합니다.

---

5. main()

• 기능: 전체 프로그램 실행의 시작점으로, Input()과 Game_Start()를 호출하여 기능을 수행합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 2000000
using namespace std;

vector<bool> isPrime;

int N;

void EesTora_Chae() {
	isPrime.resize(MAX, true);
	isPrime[0] = false;
	isPrime[1] = false;
	isPrime[2] = true;
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (isPrime[i] == false)continue;
		for (int k = i * i; k  < MAX; k += i) {
			isPrime[k] = false;
			
		}
	}
}

bool isPelindlin(int num) {
	vector<int> arr;
	while (num != 0) {
		arr.push_back(num % 10);
		num /= 10;
	}

	int startIdx = 0;
	int endIdx = arr.size() - 1;
	while (startIdx <= endIdx) {
		if (arr[startIdx] != arr[endIdx]) return false;
		startIdx++;
		endIdx--;
	}
	return true;
}


void Input() {
	cin >> N;
	EesTora_Chae();

}

void Game_Start() {
	for (int i = N; i < MAX; i++) {
		if (isPrime[i]) {
			if (isPelindlin(i)) {
				cout << i;
				return;
			}
		}
	}
}

int main(void) {
	Input();
	Game_Start();
}