[백준/BOJ] 1978번 소수 찾기 (Javascript/Node js)

1978번: 소수 찾기 (acmicpc.net)

1978번: 소수 찾기

 

문제풀이

 

처음에는 N 범위가 크지 않아서 이중 for문으로 하나하나 모든 숫자에 모든 숫자를 %연산을 돌려서 무식하게 찾아내려고 했다가. 옆에서 지켜보던 친구가 에라토스테네스의 체를 사용해보라고 말해줘서 에라토스테네스의 체가 뭐지? 하고 검색해봤다.

 

.

.

.

 

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스의 체에 대해서는 참고한 원글을 첨부하고 자세한 설명은 생략하겠다.

 

에라토스테네스의 체를 이해했다면 알고리즘은 간단해진다.

 

1. 에라토스테네스의 체를 이중 for문으로 구현하여(어떻게 구현하는지는 코드에서 주석으로 자세히 설명하도록 하겠다.) 입력받은 N가지의 수 중에서 가장 큰 수까지 소수로만 이루어진 배열을 생성한다.

2. 입력받은 수들 중에서 소수로만 이루어진 배열에 값이 포함되어 있지 않은 수는 개수로 세지 않는다.

 

 

전체코드

const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(item => item.split(" "));
const max = Math.max(...input[1]);
var nums = input[1];
var filter = [];  //에라토스테네스의 체로 소수로만 이루어진 배열
var answer = 0;


for(let i=1; i<= max; i++){
    filter[i] = i;  // 1. 배열을 입력받은 수 중 가장 큰수까지 1부터 차례로 채운다. ex ) 1 2 4 7 => filter[1, 2, 3, 4, 5, 6, 7]
}
for(let i=2; i<= max; i++){ 
    for(let j=i+1; j<= max; j++){  // Ex) i가 2라면 index 3부터 max까지 2의 배수들을 찾아내 제거한다.
        if(filter[j] % i == 0){            //  다음은 i가 3일때 3의 배수들을 찾아내 제거하고 이를 i가 max가 될때까지 반복한다.
            filter.splice(j, 1);
        }
    }
}

filter.shift();
filter.shift();

for(let i=0; i<nums.length; i++){
    for(let j=0; j<filter.length; j++){
        if(nums[i] == filter[j]) answer++;
    }
}

console.log(answer);

 

---

* 수정

 

위 코드는 에라토스테네스의 체를 생성하는 반복문의 조건에서 큰 오류가 존재했습니다. 올바른 조건은 아래의 소수구하기 게시글의 코드를 참고해주시길 바랍니다.

[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js)