소수&팰린드롬

문제

언어

  • JavaScript

순서도

  1. 넉넉한 범위까지 존재하는 모든 소수 구하기 (약 2,000,000)
  2. 주어진 N 보다 큰 소수 중에서 팰린드롬인 수 출력

문제 풀이 step 1

  • N 보다 큰 소수 중에서 팰린드롬인 수를 찾아서 출력하는 문제입니다.
  • 에라토스테네스의 체와 팰린드롬 이 2 가지의 개념에 대해서 알고 있으면 쉽게 풀 수 있는 문제입니다.
  • 우선, 에라토스테네스의 체를 이용해서 범위 내의 모든 소수를 구합니다.
    • 범위는 N 의 최댓값이 1,000,000 이므로, 이보다 크면서 팰린드롬인 소수가 존재하는 범위까지 입니다.
    • 1,000,000 보다 크거나 같으며, 소수이면서 팰린드롬인 수를 찾아보니 1,003,001 이 나왔고, 저는 넉넉하게 1,010,000 까지를 범위로 잡았습니다.
    • 범위를 정한 후에 에라토스테네스의 체를 이용해서 모든 소수를 구합니다.
  • 구한 모든 소수 중에서 N 보다 큰 소수 중에서 팰린드롬인지 검사하고, 팰린드롬인 수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 팰린드롬인지 검사하는 함수
const checkPalindrome = (prime) => {
	const str = String(prime);

	// 가장 왼쪽 index 와 가장 오른쪽 index 를 선언하고,
	// 각 index 가 가운데로 한 칸씩 이동하면서,
	// 두 인덱스가 가리키는 값이 같은지 비교하는 방식
	let [left, right] = [0, str.length - 1];
	while (left < right) {
		if (str[left++] === str[right--]) continue;
		else return false;
	}

	return true;
};

const solution = (input) => {
	const n = Number(input[0]);

	// 에라토스테네스의 체를 이용해서 범위 내의 모든 소수 구하기
	const prime = [];
	const isPrime = Array(1010000).fill(true);
	for (let i = 2; i < 1010000; i++) {
		if (!isPrime[i]) {
			continue;
		} else {
			prime.push(i);
		}

		for (let j = i + i; j < 1010000; j += i) {
			isPrime[j] = false;
		}
	}

	// 범위 내의 모든 소수 중에서 팰린드롬인 수 찾기
	let res = null;
	for (let i = 0; i < prime.length; i++) {
		if (prime[i] < n) continue;

		if (checkPalindrome(prime[i]) === true) {
			res = prime[i];
			break;
		}
	}

	return res;
};

console.log(solution(input));