소수의 연속합

문제

언어

  • JavaScript

순서도

  1. 에라토스테네스의 체를 이용해서 1 ~ 4,000,000 사이의 소수 구하기
  2. 소수들을 앞이나 뒤에서부터 구간합을 구하기
  3. 구간합이 주어진 n 과 동일한지 비교하고 경우의 수 계산

문제 풀이 step 1

  • 본 문제는 에라토스테네스의 체를 알면 쉽게 풀 수 있는 문제입니다.
  • 에라토스테네스의 체에 관련해서는 백준 1929번 - 소수 구하기 풀이 에 포스트되어 있습니다.
  • 우선 에라토스테네스의 체를 이용해서 1 ~ 4,000,000 사이의 소수를 모두 구합니다.
  • 구한 소수들을 완전 탐색 방식으로, 맨 뒤의 값(가장 큰 소수) 또는 맨 앞의 값(가장 작은 소수)을 기준으로 구간합을 구합니다.
  • 구한 구간합이 주어진 N 과 동일하다면 경우의 수를 늘려줍니다.
  • 위 과정을 통해서 구한 경우의 수를 출력하면 정답이 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 완전 탐색 방식 말고, 구간합의 처음 index 와 마지막 index 를 기억하고 조절하며, 구간합을 주어진 N 과 비교함으로써 경우의 수를 계산하는 방식으로도 풀어봤습니다.
  • 하지만 소요 시간이 차이가 나지 않아서, 좀 더 쉬운 완전 탐색 방식으로 포스트하게 되었습니다.

소스 코드

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

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

	// 소수를 모두 넣을 배열
	const prime = [];
	const isPrime = Array.from({length: MAX + 1}, () => true);
	isPrime[0] = isPrime[1] = false;

	// 에라토스테네스의 체를 이용해서 소수를 판별하고, 주어진 범위 내에서 모든 소수를 구하기
	for (let i = 2; i < MAX + 1; i++) {
		if (isPrime[i] === false) continue;
		// 배열에 모든 소수 기록
		prime.push(i);

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

	let cnt = 0;
	// 맨 뒤에서부터 하나의 값을 기준으로 구간합 구하기
	for (let i = prime.length - 1; i >= 0; i--) {
		let sum = 0;
		for (let j = i; j >= 0; j--) {
			sum += prime[j];

			if (sum === n) cnt += 1;
			if (sum >= n) break;
		}
	}

	// 경우의 수 출력
	return cnt;
};

console.log(solution(input));