[JavaScript/코딩테스트] <백준 - 17103번 골드바흐 파티션> 에라토스테네스의 체

문제

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

 

🔗분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

 

🔗문제 설명

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

 

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

🔗입력

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

 

🔗출력

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

 

---

풀이

 

 

이 문제는 소수 + 소수 = 입력값 (N)이 되는 경우를 세는 문제이다.

나는 2부터 소수이므로 2부터 시작해서 다른 반대편 숫자가 소수인지 판별하였다. 

 

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

const N = input.slice(1).map(Number);
let result = {};

N.forEach(v => {
  result[v] = 0;
});

//소수 판별
const isPrime = v => {
  if (v < 2) return false;
  if (v === 2) return true;

  for (let i = 2; i * i <= v; i++) {
    if (v % i === 0) {
      return false;
    }
  }
  return true;
};

for (let i = 0; i < Number(input[0]); i++) {
  const Number = N[i];
  let sosu_total = 0;

  for (let j = 2; j <= Number / 2; j++) {
    let anoter_number = Number - j;
    if (isPrime(j) && isPrime(anoter_number)) {
      sosu_total++;
    }
  }
  result[Number] = sosu_total;
}

N.forEach(i => {
  console.log(result[i]);
});

나의 첫 정답이다.

하지만 해당 정답은 시간초과.... 

이 코드는 소수를 판별하는 부분에서  매번 함수가 호출되어 시간 복잡도가 높아진다고 한다...

 

 

에라토스테네스의 체

 

서치를 하던 중 소수를 효율성으로 찾을 수 있는

에라토스테네스의 체 알고리즘이 있다는 것을 알게 되었다

 

const N = [1, 2, 3, 4, 5];

const maxNumber = Math.max(...N); //가장 큰 수 찾기
const isPrime = Array(maxNumber + 1).fill(true);
isPrime[0] = isPrime[1] = false;

//에라토스테네스의 체 이용
for (let i = 2; i * i <= maxNumber; i++) {
  if (isPrime[i]) {
    for (let j = i * i; j <= maxNumber; j += i) {
      isPrime[j] = false;
    }
  }
}

console.log(isPrime)

1 .배열의 최댓값을 찾는다 (해당 코드에서는 5)

 

2. 모든 숫자를 소수로 판단하고 true로 채운다 ([true, true , true , true , true , true ]) 

(배열의 인덱스 값과 실제 값을 동일시하기 위해 +1을 함)

 

3. 0과 1은 소수가 아니므로 제외한다 ([ false, false, true, true, true  , true ])

 

4. 2부터 소수인지 아닌지 판별한다.

 

해당 코드에서는 i는 2까지만 적용 가능하다

i가 2라면 j는 4가 되어 4는 소수가 아닌 false가 된다

이런식으로 소수를 찾는 방법이다  

 

시간 복잡도는 O(n log log n)이 나온다고 한다

---

 

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


const N = input.slice(1).map(Number);
let result = {};

N.forEach(v => {
  result[v] = 0;
});

//소수 판별
const maxNumber = Math.max(...N); //가장 큰 수 찾기
const isPrime = Array(maxNumber + 1).fill(true);
isPrime[0] = isPrime[1] = false;

//에라토스테네스의 체 이용
for (let i = 2; i * i <= maxNumber; i++) {
  if (isPrime[i]) {
    for (let j = i * i; j <= maxNumber; j += i) {
      isPrime[j] = false;
    }
  }
}

for (let i = 0; i < Number(input[0]); i++) {
  const Number = N[i];
  let sosu_total = 0;

  for (let j = 2; j <= Number / 2; j++) {
    let anoter_number = Number - j;
    if (isPrime[j] && isPrime[anoter_number]) {
      sosu_total++;
    }
  }
  result[Number] = sosu_total;
}

N.forEach(i => {
  console.log(result[i]);
});

위에 에라토스테네스의 체 알고리즘을 이용해서 2개의 수가 모두 소수인 경우

sosu_total을 증가시켜서 문제를  해결할 수 있었다. 

 

 

느낀점

우선 코테를 풀다보면 소수를 찾는 문제를 많이 만났는데

에라토스테네스의 체 알고리즘이라는 게 있다는 것을 첨 알게 되었다

솔직히 처음 봤을땐 for문을 2번 쓰는데 효율적일지 의심이 들었으나

로직을 이해하고 직접 사용해보니

정말 효율적이고 이걸 발견 사람이 대단하다는 것을 알 수 있었다.