[ 백준 _ 6588 ] 골드바흐의 추측 ( 수학 - 자바스크립트 )

문제

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

6588번: 골드바흐의 추측

 

How to Solve ?

4이상인 수는 2개의 소수의 합으로 만들어 낼 수 있다는 것을 증명 하는 문제이다.

 

1) 에라토스테네스의 체

 

소수의 합으로 만들 수 있는지, 없는지를 확인 하기 위해서는 우선적으로 "소수"들을 만들어 낼 필요가 있다고 생각했다.

그리하여, 1부터 주어진 값까지의 소수를 에라토스테네스의 체를 통해 미리 구해 놓았다.

 

2) 투포인터

 

부분의 합을 구할 때, 개수가 정해져있다면 투포인터을 통해 굉장히 효과적으로 구할 수 있따.

 

// 에라토스테네스의 체
function isPrime(n) {
  if (n < 2) {
    return false;
  }

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }

  return true;
}
function solution(value) {

  let primeArr = [];
  let target = value;

  for (let i = 0; i < value; i++) {
    
    if (isPrime(i)) {
      primeArr.push(i);
    }
  }
	
  // 투포인터
  let left = 0;
  let right = primeArr.length - 1;

  while (left < right) {

    let sum = primeArr[left] + primeArr[right];

    if (sum === target) {
      console.log(target + " = " + primeArr[left] + " + " + primeArr[right]);
      break;
    } 
    
    else if (sum < target) {
      left++;
    } 
    
    else if (sum > target) {
      right--;
    }

  }
}

let nums = [8, 20, 42];
console.log(solution());

for (let i = 0; i < nums.length; i++) {
  solution(nums[i]);
}