(Silver4) 백준 2960 에라토스테네스의체 (JavaScript, Node.js)

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

• 2부터 N까지 모든 정수를 적는다.
• 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
• P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
• N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제1 입력

7 3

예제1 출력

6

예제2 입력

15 12

예제2 출력

7

예제3 입력

10 7

예제3 출력

9

풀이 과정

• 문제 설명을 보고 소수문제라고 생각할 수 있으나 읽어보면 배열의 최솟값의 배수들을 지우고, 그 다음 최솟값의 배수를 지우고... 를 반복하여 지워진 숫자가 K 번째에 해당할 경우 그 값을 리턴하는 문제이다. 소수는 아니고 배열 다루기 문제
• K번째에 해당할 경우 바로 배열을 빠져나와야하므로 forEach 가 아닌 some 을 활용했다. some메서드는 콜백함수가 true를 반환할 경우 바로 메서드를 종료한다.
• 원본배열에 변화를 가하는 splice 메서드를 이용해 계속 배수들을 지워주고, count가 K에 해당할 경우 반복문에서 빠져나와 answer에 담긴 수를 반환한다.

정답 풀이

const fs = require('fs');
const root = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [a, b] = fs.readFileSync(root, 'utf8').toString().trim().split(' ').map(a => +a);

console.log(solution(a,b));

function solution(a, b) {
    let arr = [];
    let count = 0;
    let answer = 0;
  
  	// 2~a 까지의 배열 생성
    for(let i = 2; i <= a; i++) {
        arr.push(i);
    }
  
    while(count < b){
        prime = arr[0];
      // some메서드로 배열을 순회하며 정답을 찾았을 경우 반복문 종료
        arr.some(number => {
            if(number % prime === 0) {
                arr.splice(arr.indexOf(number), 1);
                answer = number;
                count += 1;
            }
            if(count === b) return true;
        })
    }

    return answer;
};