프로그래머스 코딩테스트 연습 Level 1 - 소수 찾기 (JavaScript)

프로그래머스 코딩테스트 연습 Level 1 - 소수 찾기 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 1 중,

[소수 찾기] 문제를 JavaScript로 해결 해보도록 하겠습니다.

 

문제

문제 설명

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

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

 

제한 조건

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

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

작성한 답

solution.js

function solution(n) {
    var prime = Array(n+1).fill(true).fill(false, 0, 2);
    for(var i=2; i<=Math.sqrt(n); i++)
        if(prime[i])
            for(var j=i*i; j<=n; j+=i)
                prime[j] = false;
    return prime.filter(el => el).length;
}

 

설명

정말 간단한 문제인데 효율성 테스트 때문에 조금은 헤맸습니다.

정말 기본적인 방법으로 소수는 1과 n만을 약수로 가진다는 것으로 계속 반복해서 방법,

소는 n은 n의 제곱근보다 크지 않은 소수로 나눠지지 않는다는 것으로 계손 반복해서 확인하는 방법,

위 방법들을 배열로도 만들어보고 그저 숫자 더하기 식으로도 해봤지만 모두 효율성 테스트에서 시간초과가 납니다.

그래서 에라토스테네스의 체를 사용하여 문제를 해결했습니다.

에라토스테네스의 체란 n의 제곱근에 보다 작은 소수의 배수들을 계속해서 제외해주면 결국 소수만 남는다는 공식으로, 마치 소수의 배수들을 체에 수를 걸러낸다고 하여 이름붙였다고 합니다.

 

그럼 에라토스테네스의 체를 참고로한 코드를 설명드리도록 하겠습니다.

먼저 true 값을 가지는 n + 1 개의 배열을 생성합니다. n+1개인 이유는 만약 n이 10 이라면 0부터 10 까지를 의미하는 11개의 요소를 가지는 배열을 생성하기 위해서 입니다.

그리고 index 0 부터 2개의 요소는 false로 변경해줍니다. 왜냐하면 0과 1 은 소수로 치지는 않기 때문입니다.

배열을 생성하셨으면 가작 작은 소수인 2 부터 반복을 돌립니다.

2부터 시작하여 2의 모든 배수 index에 있는 요소들을 모두 true 에서 false로 변경해줍니다.

그럼 false인 요소들을 소수가 아니라는 의미가 됩니다.

이미 false가 된 요소들은 소수가 아니기 때문에 반복을 돌릴 필요가 없기 때문에 조건도 미리 걸어줍니다.

그렇게 모든 반복이 끝나면 배열에는 소수인 index에는 true가, 소수가 아닌 index에는 false가 들어가 있을 것입니다.

그러므로 배열을 filter로 true만 걸러내고, 걸러낸 배열의 길이를 반환하면,

1부터 n까지의 소수의 개수를 구할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청 사항은 언제든지 말씀 해주세요!

 

감사합니다.