✨ Lv. 1 - 소수 찾기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12921
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한사항
- n은 2이상 1000000이하의 자연수입니다.
풀이 코드 + 설명
단순히 문제를 접했을때는 1부터 n까지 각각의 수가 소수인지를 판별하여 그 개수를 return 하는 방식으로 풀이를 시도하였습니다. 하지만 이러한 방법으로 코드를 작성할 경우, 이중 for문으로 시간복잡도가 O(n^2) time에 해당하게 됩니다. 해당 문제의 n의 크기는 최대 10000000이므로 polynomial time이 걸리는 해당 풀이법으로는 시간 초과가 발생하게 됩니다.
그렇다면 이보다 더 효율적으로 소수를 찾는 방법은 어떤 것이 있을까요? 가장 유명한 방법인 에라토스테네스의 체에 대해서 알아보고 넘어갑시다.
에라토스테네스의 체
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.
- 2부터 순서대로 소수를 찾아 각 소수의 배수들을 모두 제외시킵니다.
단순하게 글로만 읽어봤을 때는 애매한 설명이니, 위 그림을 통해 그 과정을 살펴봅시다. 이러한 방법으로 소수를 대량으로 빠르고 정확하게 구할 수 있습니다. 이를 코드로 표현해보겠습니다.
function solution(n) {
let result = Array.from({length: n - 1}, (_, i) => i + 2);
let answer = 0;
for(let i = 0; i < result.length; i++) {
if(result[i] !== -1) {
answer++;
const curPrime = result[i];
for(let j = 2; j * curPrime - 2 <= result.length; j++) result[j * curPrime - 2] = -1;
}
}
return answer;
}우선 Array.from을 이용하여 2부터 n까지의 수가 순서대로 담겨있는 배열을 생성합니다. 이후, 해당 배열을 순회하며 에라토스테네스의 체를 이용해 소수를 구별합니다.
소수의 배수라고 판별된 수들은 -1로 값을 변경합니다. -1이 아닌 숫자라면, 해당 숫자는 소수이므로 배열에서 소수의 배수들을 모두 -1로 변경해줍니다.
