백준2960번 - 에라토스테네스의 체 자바스크립트(Node.js)풀이

문제

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

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

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

 

 

입력

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

 

출력

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

 

 

문제유형

수학

구현

정수론

소수 판정

에라토스테네스의 체

 

 

---

에라토스테네스의 체를 몰라도 문제만 잘 읽으면 풀 수 있는 문제이다.

나중에 소수판정을 할때 많이 사용될거같아서 따로 포스팅하며 정리해보도록 하겠다.

 

 

 알고리즘을 시작할때 배우는 가장 기본적인 소수판정 알고리즘은 숫자 n을 2부터 n까지 직접 나누어 보는 방법을 사용한다. 하지만 이러한 방법은 O(N)의 시간 복잡도를 갖게 된다. 하지만 에라토스테네스의 체로 문제를 해결하게 된다면 O(nlog logn)의 시간 복잡도로 문제를 해결할 수 있다. (아래 위키피디아 참조)

 

 

 

Sieve of Eratosthenes - Wikipedia

 

 

 

전체코드

const fs = require('fs');
const stdin = (process.platform === 'linux'
        ? fs.readFileSync('/dev/stdin').toString()
        : `10 7`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

let a = [];
let count = 0;
let inVal = input().split(' ').map(Number);
let maxNUm = inVal[0];
let findNum = inVal[1];

for(let i=0; i<=maxNUm; i++){
    a.push(i);
}

function answer(){
    for(let i=2; i<=maxNUm; i++){
        for(let j= i; j<=maxNUm; j += i){
            if(a[j] == 0) continue;
            a[j] = 0;
            count += 1;
            if(count == findNum){
                console.log(j);
                return;
            }
        }
    }
}
answer();