[프로그래머스] 소수찾기

문제 링크

1️⃣ 문제 설명

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

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

---

2️⃣ 제한 사항

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

3️⃣ 입출력 예

4️⃣ 나의 풀이

function solution(n) {
    let answer = 0;
    const arr = new Array(n+1).fill(true); // 초깃값 설정
    const end = Math.sqrt(n) 
    
    for(let i = 2; i <= end; ++i){
        // 이미 소수가 아닌 인덱스는 스킵
        if(arr[i] === false){
            continue; 
        }
        // 소수가 아닌 데이터는 false
        for(let k = i * i; k <= n; k += i){
            arr[k] = false;
        }
    }
    // 소수의 갯수
    for(let i = 2; i <= n; ++i){
        if(arr[i] === true){
            answer++;
        }
    }
    return answer;
}

• 에라토스테네스의 체
  1.2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당
  2.2는 소수이므로 오른쪽에 2
  3.자기 자신을 제외한 2의 배수를 모두 삭제
  4.남아있는 수 가운데 3은 소수이므로 오른쪽에 3
  5.자기 자신을 제외한 3의 배수를 모두 삭제