[Programmers/JS] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

1. 문제 풀이

• 에라토스테네스의 체를 그대로 구현해야 하는 문제. (아래 링크 참조) (https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)
• 자기 자신(n)도 포함해야 하므로 index를 맞춰주기 위해 n+1의 boolean 배열을 선언해 주고, 값은 모두 true로 설정해 준다. (일단, 모든 수가 소수라고 가정한다.)
• 0과 1은 소수가 아니므로 arr[0]과 arr[1]은 false로 미리 설정 하였음.
• 첫 번째 반복문은 2부터 n까지를 순회하도록 설정 한다.
• 만약 (arr[i] === true) i가 소수라면 자기 자신을 제외한 자신의 모든 배수들은 소수가 아니므로, 두 번째 반복문을 통해 소수가 아님을 체크한다. (arr[j] = false)
• arr 안의 true의 갯수를 더해 answer로 반환한다.

 

 

2. 제출 코드

function solution(n) {
    let answer = 0;
    let arr = Array.from({length:n+1}, () => true) // 모두 소수라고 가정
    arr[0] = false; arr[1] = false;
    
    for(let i = 2; i < n+1; i++) {
        
        if(arr[i]) {
            for(let j = i+i; j <= n; j+=i) {
                arr[j] = false;
            }
        }
    }
    arr.map((isPrime) => {
        if(isPrime === true) answer++;
    })
    return answer
    
    
}