(자바스크립트 알고리즘) 소수 찾기 - kimyang-sun

자바스크립트 알고리즘 (Programmers)

---

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

---

문제 풀이

function solution(n) {
    let arr = [];
    for (let i = 2; i <= n; i++) {
        arr[i - 2] = i;
    }
    for (let i = 2; i <= n; i++) {
        for (let j = i + i; j <= n; j += i) {
            arr[j - 2] = 0;
        }
    }
    
    const answer = arr.filter((value) => value);
    return answer.length;
}

풀이입니다.

 

1은 제외하고 반복문으로 i = 2 부터 시작해서 n까지 반복합니다.

 

이 때, arr[i - 2] = i 를 해줌으로써 숫자가 정렬된 배열을 만듭니다.

 

그 배열에서 마찬가지로 1을 제외하고 2부터 n 까지 반복하는 반복문을 만들어주고

 

그 안에서 2중으로 반복문을 사용하여 n보다 작은 수에서 2의 배수 3의 배수 4의 배수 등에 포함되는 부분들을

 

0으로 바꾸어 줍니다.

 

그리고 filter() 를 통해서 0으로 변하지 않은 소수들만 answer 에 넣어주고 answer.length 를 리턴해줍니다.

 

다른 사람들의 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}