Node.js)백준 15711번: 환상의 짝꿍

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

15711번: 환상의 짝꿍

 

 

*에라토스테네스의 체로 소수구하기  2000000까지 소수 구하기. 

 

 

*골드바흐 추측

짝수일 때. 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시 가능

홀수일 때, 2 + 소수 로 표시가능하면됨.  두 수의 합 - 2 가 소수면 됨. 

 

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n').map(v=>v.split(' ').map(Number));
const N = input.shift()[0];
const answer = [];

let prime = new Array(2000000).fill(true) //true면 소수
const temp_sqrt =  Math.ceil(Math.sqrt(2000000));
prime[0] = false;
prime[1] = false;
for(let i =2; i<=temp_sqrt; i++){
  if(!prime[i])continue;
  let flag = true;
  for(let j = 2; j<i; j++){
    if(i%j==0){
      flag = false;
      break;
    }
  }
  if(flag){
    for(let k = i+i; k<=2000000; k+=i){
      prime[k]=false
    }
  }
}

const prime_list = [];

prime.forEach((v,i)=>{
  if(v){
    prime_list.push(i)
  }
})


input.forEach(v=>{
  const [a,b] = v;
  const S = a+b
  answer.push(checkDoublePrime(S))

})
console.log(answer.join('\n'))

function checkDoublePrime(x){
  if(x<4) return "NO"   // 2,3일때 
  if(x%2==0){
    return "YES" // 짝수일 때, <- 골드바흐의 추측
  }else{
    let y =  x-2
    if(prime[y]) return "YES"
    for(let i = 0; i<prime_list.length; i++){
      if(y%prime_list[i]==0) return "NO"
    }
    return "YES"
  }
}