[프로그래머스 스킬체크 레벨 1] 소수 찾기 풀이 및 설명 - 자바스크립트[JavaScript]

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

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

 

문제

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 

 

제한 사항

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

결괏값 예시

 

n	result
10	4
5	3

 

기본 제공 틀

 

function solution(n) {
    var answer = 0;
    return answer;
}

 

풀이 [JavaScript]

 

728x90

첫번째로 풀었던 방식은 (1은 소수가 아니므로) 2부터 n까지의 값을 돌면서 1부터 n 자기 자신의 수까지 값을 돌며 나머지가 0으로 나누어 떨어지면 count를 올렸고, count가 2보다 작거나 같으면 answer값에 해당 숫자를 추가하는 형식으로 로직을 짜보았습니다.

 

이렇게 했을 경우, 테스트 9번까지는 통과할 수 있었지만, 테스트 10번 이후와, 효율성 테스트에서는 실패했습니다.

function solution(n) {
    var count =0;
    var answer = 0;
    for(var i = 2; i<=n ; i++){
        for(var j = 1; j<=i; j++){
            if(i % j === 0){
                count++;
            }
        }
        if(count <= 2){
            answer++;
        }
        count = 0;
    }
    return answer;
}

다음으로는 에라토스테네스의 체를 활용해보았는데요.

개념은 간단합니다. 소수의 배수들을 제거해나가면 결국 소수들만 남는 방식인데요.

인덱스는 0부터 시작하기 때문에, 1은 인덱스 0에서부터 시작하면 로직을 구현하는데 복잡해질 수 있습니다.

그래서 인덱스 0에는 숫자 0이 있다는 가정하에, true로 구성된 배열을 n을 포함하여 생성했습니다.

그리고, 숫자 0과 1은 소수가 아니므로,  false로 지정을 했습니다.

숫자 2부터 n까지의 인덱스를 돌면서, 만약, i번째 값이 true인 경우(소수인 경우)에만 배열을 돌고, 소수는 2, 3, 5와 같이 시작하므로, 소수의 배수는 2*2, 2*3...이렇게 계산되어야 하므로, k는 2부터 돌면서 n/소수로 나눈 수만큼만 돌면서 (i가 2이고 n이 10인 경우, 10/2인 5까지만 2*5까지만 돌아야하므로) arr[i*k](2*2, 2*3, 2*4, 2*5)인 인덱스들을 모두 false로 바꾸어주었습니다.

 

이렇게 되면, for문이 n까지의 모든 값을 돌지 않아도 되므로, 효율성이 훨씬 개선될 수 있습니다.

function solution(n) {
    var arr =[];
    for(var i=0; i<=n; i++){
        arr.push(true);
    }
    
    arr[0] = false;
    arr[1] = false;
    
    for(var i=2; i<=n; i++){
        if (arr[i]) {
            for(var k=2; k<=n/i; k++){
                arr[i*k] = false;
            }
        }
    }
    
    return arr.filter(bool => bool === true).length;
}

 

채점 결과 [JavaScript]