문제

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

풀이(시간초과)

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
input.shift();
let inputArray = input.map(Number)

  function generatePrimes(n){
    let arr = [];
    let sleve = Array.from({length:n+1}, ()=>true)
    sleve[0] = false;
    sleve[1] = false;

    for(let i = 2; i<=Math.sqrt(n); i++){
      if(sleve[i]){
        for(let j = i * i; j<=n; j+=i){
          sleve[j]= false;
        }
      }
    }

    for(let i = 2; i<sleve.length; i++){
      if(sleve[i]) arr.push(i)
    }
    
    return arr;
  }
  

  function twoPointer(num){
    let arr = generatePrimes(num)
    let left = 0;
    let right = arr.length-1;
    let answer = [];
    while(left<=right){
      let sum = arr[left]+arr[right];
      if(sum === num){
        answer.push([arr[left],arr[right]])
        left++;
        right--;
        if (left > right) {
            break;
        }
          
      }else if(sum < num) left++;
      else right--;
    }
    
    return answer.length;
  }

  for(let x of inputArray){
    console.log(twoPointer(x))
  }  

받아온 수들의 배열을 하나씩 검사해서 수 만큼의 소수 배열을 만들고 투포인터 알고리즘으로 두 소수의 합이 num과 같은 것들을 따로 뺄려고 하니까 시간초과가 났다. 그래서 다른 방법으로 풀어야 하는건가 싶어서 다른 사람들의 풀이를 보고 문제를 해결하였다.

수정한 풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
input.shift();
let number = input.map(Number)
let answer = [];
  let maxNum = Math.max(...number)
  let sleve = Array.from({length:maxNum+1}, ()=>true)
    sleve[0] = false;
    sleve[1] = false;

    for(let i = 2; i<=Math.sqrt(maxNum); i++){  
      if(sleve[i]){
        for(let j = 2; j <= (maxNum / i); j++){
          sleve[i * j] = false;
        }
      }
    }    
  
  for(let x of number){
    let count = 0;
    for(let i = 2; i<=(x/2); i++){  
        if(sleve[i] && sleve[x-i]) count++
    }
    answer.push(count);
  }  
  console.log(answer.join('\n'))

1. 받아온 수들의 최대 수를 구해서 그보다 작은 소수들을 모두 구한다(받아온 수들의 갯수만큼 배열을 만들지 않아도 되어서 수행속도가 빨라짐)
2. 에라토스테네스의 체 알고리즘으로 소수를 구해주고 배열을 리턴시킨다.
3. number를 하나씩 탐색하면서 배열에 값이 두 소수로 합해지면 count를 증가시킴