(JavaScript) 백준 1644 소수의 연속합 (JS)

SanE·2024년 6월 13일

JavaScript algorithm two pointer 백준 소수 찾기 에라토스테네스의 체

Algorithm

목록 보기

112/127

소수의 연속합

📚 문제 설명

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)

숫자 N이 주어질 때, 연속된 소수의 합으로 구할 수 있는 경우의 수를 구하여라.

👨🏻‍💻 풀이 과정

문제를 풀기 위해서는 우선 N 이하의 소수를 모두 구할 필요가 있어 보인다.
소수를 찾기 위해 가장 대표적인 알고리즘인 에라토스테네스의 체를 사용해 보자.

💡에라토스테네스의 체 (소수 찾기)

에라토스테네스의 체는 기본적으로 배열을 이용한다.

예를 들어 아래와 같은 표가 있다고 하자.

ID	2	3	4	5	6
Value	2	3	4	5	6

우선 가장 작은 소수 2부터 순차적으로 진행해보자

ID 3 : 2의 배수가 아니기 때문에 넘어감.
ID 4 : 2의 배수이다. Value 2로 변경.
ID 5 : 2의 배수가 아니라 넘어감.
ID 6 : 2의 배수이다. Value 2로 변경.

ID	2	3	4	5	6
Value	2	3	2	5	2

이렇게 진행하면, ID 값과 Value 값이 일치하면 소수이다.

이제 코드를 확인해보자.

에라토스테네스의 체 (소수 찾기)

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    const N = parseInt(input[0]);
	// 배열.
    let PrimeNumber = Array.from({length: N + 1}, (value, index) => index);
	// 에라토스테네스의 체.
    for (let i = 2; i * i < PrimeNumber.length; i++) {
        if (PrimeNumber[i] === i) {
            for (let j = i * i; j < PrimeNumber.length; j += i) {
                if (j % i === 0 && PrimeNumber[j] === j) {
                    PrimeNumber[j] = i;
                }
            }
        }
    }

위의 코드를 보면 반복문에 수상한 부분이 보인다.
for (let i = 2; i * i < PrimeNumber.length; i++) 이 반복문 안에 i * i < PrimeNumber.length;
두번째 반복문 for (let j = i * i; j < PrimeNumber.length; j += i) 안에 let j = i * i;

왜 이 두 부분에는 제곱근으로 구하는 걸까??
그 이유는 아래 두개의 이유이다.

약수의 대칭성
- n = a * b 라면 a,b 둘 중 하나는 반드시 $\sqrt{n}$ 이다.
중복 제거
- 제곱근을 넘는 수의 배수들은 이미 더 작은 수의 배수로 제거된다.

그럼 이제 소수를 찾았으니 다음 풀이를 생각해보자.

💡 Two Pointer

연속된 소수의 합이라고 했기 때문에 소수를 구했으면, 이제 간단하다.

2개의 포인터 left, right 를 이용.
소수의 합이 N 보다 작으면 right++
소수의 합이 N 보다 크면 left++
위의 과정을 right 가 끝까지 갈 때까지 반복.

전체 코드

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
    const N = parseInt(input[0]);
	// 소수 배열.
    let PrimeNumber = Array.from({length: N + 1}, (value, index) => index);
	// 에라토스테네스의 체
    for (let i = 2; i * i < PrimeNumber.length; i++) {
        if (PrimeNumber[i] === i) {
            for (let j = i * i; j < PrimeNumber.length; j += i) {
                if (j % i === 0 && PrimeNumber[j] === j) {
                    PrimeNumber[j] = i;
                }
            }
        }
    }
	// 소수 중복 제거, 1 제거.
    PrimeNumber = PrimeNumber.filter((value,index) => value === index && value > 1);
	// 투 포인터 사용 시작.
	// 변수 생성.
    let left = 0;
    let right = 0;
	// 합한 수.
    let sum = 0;
	// 만족하는 경우의 수
    let cnt = 0;

    while (right <= PrimeNumber.length) {
      	// 조건 만족시.
        if (sum === N) {
            cnt++;
        }
		// 너무 크면 left 한칸 제거.
        if (sum >= N) {
            sum -= PrimeNumber[left++];
        } else {
          // 작다면 right 한칸 증가.
            sum += PrimeNumber[right++];
        }
    }
    console.log(cnt);