[Programmers Level 1] 소수찾기 Javascript

⚡문제정보

 

1부터 입력받은 숫자 n사이의 모든 소수의 개수를 반환하는 문제입니다.

처음엔 이중for문으로 구현했는데 그렇게 문제를 풀었더니

효율성 테스트에서 멸망했습니다.

 

---

 

 

🔍나의 첫번째 풀이

 

function solution(n) {
    let answer = 0
    for(i=2 ; i<=n ; i++) {
        if(i != 2 && i % 2 == 0) continue
        let counter = 0
        for(j=2 ; j <= Math.sqrt(i); j++ ) {
            if(i % j == 0) {
                counter = counter + 1
            }
        }
        if(counter == 0) {answer++}
    }
    return answer
}

for문을 이중으로 돌린게 문제인듯 하네요

 

검색해본 결과 에라토스테네스의 체라고 하는 소수찾기 알고리즘을 사용해야하는구나 하는 결론

🔍도와줘요 구글신

function solution(num) {
	let arr = Array(num + 1).fill(true);
    arr[0] = false;
    arr[1] = false;
   
    for(let i = 2; i * i <= num; i++) { 
        if(arr[i]) {
            for(let j = i * i; j <= num; j += i) {
                arr[j] = false; 
            }
        }
    }
    return arr.filter(el => el).length
}

num의 +1만큼의 길이로 구성된 배열을 선언해주고 모든 요소를 true로 채워줍니다.

0과 1은 소수가 아니니까 false로 만들어주고

for문을 돌려주면 되는군요

 

에라토스테네스의 체

 

에라토스테네스의 체 구현은 아래 블로그에서 구현되어 있던 코드를 참고로 했습니다.

https://peach-milk.tistory.com/entry/%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

소수 구하기 (자바스크립트)