[백준] 소수&팰린드롬 (1747번)

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입력 1 복사

31

예제 출력 1 복사

101

---

소수와 팰린드롬의 개념을 합한 문제다.

소수이면서 팰린드롬인 N보다 같거나 큰 최소한의 값을 출력해야 한다.

소수는 에라토스테네스의 체를 이용해 쉽게 구할 수 있다.

팰린드롬또한 수를 string 으로 형변환 한 후에 일일이 검사해주면 된다.

문제는 N이 1000000인 경우 백만보다 같거나 큰 최소한의 소수를 구하는 게 중요하다. 

소수 배열을 1004000정도까지 선언한 후 구해주면 1003001이 백만을 넘는 최소한의 소수이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%86%8C%EC%88%98%2C%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC%20(1747%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <memory.h>
#include <algorithm>
#include <string>
using namespace std;
bool isPrime[1004000];
int N;

void erathos() {
	memset(isPrime, true, sizeof(isPrime));
	isPrime[1] = false;

	for (int i = 2; i * i < 1004000; i++) {
		if (isPrime[i] == false) continue;
		for (int j = i + i; j < 1004000; j += i) {
			isPrime[j] = false;
		}
	}
}

bool isPalin(int n) {
	string str = to_string(n);
	for (int i = 0; i < str.size() / 2; i++) {
		if (str[i] != str[str.size() - i - 1])
			return false;
	}
	return true;
}

int main()
{
	cin >> N;

	erathos();

	for (int i = N;; i++) {
		if (isPrime[i] == false) continue;
		if (isPalin(i)) {
			cout << i;
			break;
		}
	}
}