[JS] 소수 찾기 (에라토스테네스의 체)

소수는 1과 자기 자신만을 약수로 가지는 수를 말한다.

소수를 구하는 대표적인 방법으로는 brute force로 제곱근까지 단순 나눗셈을 하는 방법, 에라토스테네스의 체가 있다.

 

에라토스테네스의 체를 구현해보고, gpt와 함께 개선점을 찾았다

 

에라토스테네스의 체 O(N * log log N)

에라토스테네스의 체는 다수의 소수(2~n)를 빠르게 구할 수 있는 알고리즘이다.

 

2부터 시작해서, 방문한 수의 모든 배수를 지우는 방법이다 (배수는 당연히 소수가 아니므로)

결과적으로 남은 수는 모두 소수이다.

위키백과/에라토스테네스의 체

 

첫번째 코드

개념을 보고 적용한 방법이다.

function solution(n) {
    var answer = 0;
    
    const arr = Array(n+1).fill(true) // n+1 만큼의 배열을 선언 (true로 초기화해서 모두 소수라고 가정)
    for(let i = 2; i<Math.sqrt(n)+1; i++){ // 2~n의 제곱까지만 확인
        if(arr[i]){ // 체크가 되어있으면 (= 소수이면) 
            for(let j=2; i*j<=n; j++) // 해당 값의 배수를 모두 지움
                arr[i * j] = false;
        }
    }
    
    for(let i=2; i<=n; i++){
        if(arr[i] === true) answer++
    }
    
    return answer;
}

첫번째 코드의 실행 결과

 

해당 코드의 개선사항은 다음과 같다.

---

개선 코드 1 

gpt에서 말한 개선사항을 반영해보았다.

 

1. 에라토스테네스의 체는 2부터 시작하므로, 조건문으로 0,1을 미리 제외했다.

2. for문을 돌면서 제곱근을 구하는 공식을 반복적으로 계산하여, 변수로 빼서 한번만 계산했다.

3. 소수의 배수를 구하는 내부 반복문에서 i의 배수(=j)만 구하도록 변경했다. (i 이전의 값들은 모두 걸러졌기때문에)

function solution(n) {
    var answer = 0;
    
    if(n<2) return 0; // 0,1은 미리 제외
    
    const arr = Array(n+1).fill(true) // 에라토스테네스의 체
    arr[0] = arr[1] = false; // 0,1은 미리 제외
    
    const limit = Math.sqrt(n); // 제곱근 반복 계산 막기
    for(let i = 2; i<=limit; i++){ // 2~n의 제곱까지만 확인
        if(arr[i]){ // 체크가 되어있으면 (= 소수이면) 
            for(let j=i*i; j<=n; j+=i) arr[j] = false;// 해당 값의 배수를 모두 지움(i보다 작은 배수는 이미 지워졌으므로 i의 배수부터 시작)
        }
    }
    
    for(let i=2; i<=n; i++){
        if(arr[i]) answer++
    }
    
    return answer;
}

 

이전 결과에서 최대 실행 시간이 줄어들었고(18.50ms -> 16.69ms), 효율성 테스트에서 크게 시간이 줄었다.(52.01ms -> 16.58ms)

개선 1의 실행 결과

---

개선 코드 2

에라토스테네스의 체의 계산과정을 별도의 함수(findPrimes)로 분리했다.

해당 함수에서 계산 과정은 이전 코드와 동일한데, 반환하는 값을 소수만 담은 배열을 반환하도록 했다.

 

그래서 호출하는 곳에서는 해당 배열의 길이만으로 n까지의 소수 개수를 구할 수 있다.

function findPrimes(n){
    if(n<2) return 0; // 0,1은 미리 제외
    
    const arr = Array(n+1).fill(true) // 에라토스테네스의 체 
    arr[0] = arr[1] = false; // 0,1은 미리 제외
    
    const limit = Math.sqrt(n); // 제곱근 반복 계산 막기
    for(let i = 2; i<=limit; i++){ // 2~n의 제곱까지만 확인
        if(arr[i]){ // 체크가 되어있으면 (= 소수이면) 
            for(let j=i*i; j<=n; j+=i) arr[j] = false;// 해당 값의 배수를 모두 지움(i보다 작은 배수는 이미 지워졌으므로 i의 배수부터 시작)
        }
    }
    
    return arr.reduce((primes, isPrime, idx) => {
        if(isPrime) primes.push(idx)
        return primes
    }, [])
}

function solution(n) {
    const primes = findPrimes(n);    
    return primes.length;
}

 

실행 시간은 개선 코드보다 조금 늘어났는데, findPrimes에서 reduce를 사용하면서, 메모리 할당과 배열 순회 작업으로 늘어난 것 같다. 

개선 2의 실행 결과

 

결론 

에라토스테네스의 체는 고정된 범위 내의 소수를 빠르게 구하는데 효율적이다. 

하지만, 고정적으로 메모리를 잡고 계산하기 때문에 동적으로 조합되는 것과 같이 가변적으로 숫자가 바뀔때는 범위를 미리 예상하고 배열을 선언하는 거은 비효율적이다.

 

따라서 고정된 범위에서 소수를 구할 때는 에라토스테네스의 체,

숫자의 범위가 가변적일 때는 제곱근까지 단순 반복문을 돌려 계산해야한다.

 

프로그래머스