[백준 17103번 골드바흐 파티션 - node.js] [알고리즘 기초 1/2]

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

17103번: 골드바흐 파티션

 

문제

 

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

 

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력

 

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

 

예제 입출력

 

입력	출력
5 6 8 10 12 100	1 1 2 1 6

 

풀이[node.js]

 

 

728x90

이번 문제는 골드바흐의 추측을 그대로 가져와서 쓰면 된다.

가장 큰 max값을 구한 후, 그 값까지 arr에 true를 넣어주고, 0과 1은 소수가 아니므로, false를 넣어준다.

그리고, max값의 반만을 돌면서 arr의 m번째 값이 true라면, 그의 배수들을 모두 false로 바꿔준다.

 

주의할 점은, splited의 길이의 반만 돌아서, 3+3인 경우와 같이 중복이 되는 경우에도 count가 되지 않도록 해야한다.

splited의 반까지만 돌면서, arr에 splited값에서 1부터 차근차근 빼주면서 n값과 splited-n값이 존재한다면, splited를 이룰 수 있는 두 소수가 존재하는 것이므로, count++를 해주면 된다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
var result = [];
var size = Math.max(...inputs);
var arr = [];
for(var i=0; i<size; i++){
    arr.push(true);
}
arr[0] = false;
arr[1] = false;

for(var m=2; m<=size/2; m++){
    if(arr[m]){
        for(var n=2; n<=size/m; n++){
				arr[m*n] = false;
			}
    }
}

for(var k=1; k<inputs.length; k++){
    var splited = Number(inputs[k]);
    var count = 0;
    for (var n=1; n<=splited/2; n++){
        if(arr[splited-n] && arr[n]){
            count++;
        }
    }
    result.push(count);
}
console.log(result.join('\n').trim());