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

링크

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

---

문제 설명

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

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

---

제한 조건

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

---

문제 풀이

1) 코드 설명

 (1) n까지의 배열의 인덱스에 true를 넣는다 - 나중에 true면 소수, false면 소수가 아닌 수로 체크

 (2) 2 ~ n의 제곱근까지만 for문을 반복한다 - 

 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다는 것이다.

 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

 (3) i의 제곱부터 n까지 i씩 늘려가면서 false 처리한다. 

 (4) 0과 1은 소수가 아니므로 false 처리한다.

 

2) 코드

function solution(n) {
    var arr = [];
    var cnt = 0;
    for (var i = 0; i < n + 1; i++) {
        arr.push(true);
    }
    
    for (var i = 2; i * i <= n; i++) {
        if (arr[i]) {
            for (var j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    arr.splice(0, 2, false, false);
    for(var i = 0; i <arr.length; i++) {
        if(arr[i]) cnt++;
    }
    
    return cnt++;
}