-
[프로그래머스 Level 1] 소수찾기알고리즘 문제풀이 2020. 1. 7. 20:37
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4 5 3
위 문제를 처음 접했을 땐 평범한 소수찾기 문제인 거 같아서 매우 쉽다고 생각을 했다.
근데 범위 내에서 소수를 구하는 문제이기 때문에 에라토스테네스의 체를 활용하는 게 좋겠다는 생각이 들었다.
그럼 한 번 구현해보자.
function solution(n){ var answer = Array(n+1).fill(1); // ㉠ answer[1] = 0; answer[0] = 0; for(var j = 2; j <= Math.sqrt(n); j++){ // ㉡ for(var k = j; j * k <= n; k++){ // ㉢ answer[j * k] = 0; } } var count = 0; for(var num in answer) if(answer[num]) count++; return count; }
위의 식에서 ㉠으로 인해 계속 효율성 문제가 발생했었다.
이전 식에선 answer이라는 배열에 n이 10이면 [0,,,,10] 이런 식으로 각 인덱스에 해당하는 값을 할당해주었다.
이러니 효율성에서 떨어질 수 밖에 없었다. 에라토스테네스의 체를 이용하는 경우, 인덱스를 통해 해당 수가 소수인지 아닌지를 판별하기 때문에 인덱스에 대응하는 값은 중요하지 않다. 고로 ㉠처럼 1로 채워주는 게 효율적이다.
㉡에서 Math.sqrt를 이용해주는 것도 효율성 측면에서 매우 중요하다.
어떤 수 n이 있을 때, 이 수는 n이하의 소수의 곱으로 구성된다.
즉, n은 약수로 Math.sqrt(n) 이하의 소수(n의 제곱근 이하의 소수)를 가질 것이다. ex) 49 = 7 * 7, 42 = 2 * 3 * 7
그렇기 때문에 ㉡처럼 n의 제곱근보다 작은 수의 범위에서 소수를 찾는 것만으로도 해결이 가능하다.
위와 마찬가지 이유로 ㉢에서 var k = j를 해줌으로써, 조금 더 효율적으로 해결할 수 있게 된다.
'알고리즘 문제풀이' 카테고리의 다른 글
[APAS] Roman to Integer (0) 2020.03.29 [프로그래머스 Level 1] 약수의 합 (0) 2020.01.07