[클라우딩 어플리케이션 엔지니어링 TIL] - DAY 19

소수 판별하기

현재 숫자가 소수인지 판별하는 알고리즘을 작성할 때

가장 단순한 방법은 n까지 반복문을 돌면서 1 이외의 약수가 있는지 확인하는 것이다.

function isPrime(n) {
    for (let i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

이 알고리즘의 시간복잡도는 O(n) 여기서 조금 최적화를 해보자면

특정 수의 약수는 가운데 약수를 기준으로 대칭성을 가지므로 제곱근까지만 확인해 보면 된다.

• ex) 16 => 1, 2, 4, 8, 16
• 1 x 16 = 16
• 2 x 8 = 16
• 4 x 4 = 16

function isPrime(n) {
    for (let i = 2; i * i <= n; i++) {
        if (num % i == 0) return false;
    } 
    return true;
}

최적화한 알고리즘의 시간복잡도는 O(sqrt(n))

여기서 더 최적화할 수도 있지만 판별해야 할 수가 많지 않을 땐 이런 단순한 코드로도 충분하고,

많은 수를 판별해야 할 때는 여기서 더 최적화를 해봐야 크게 의미가 없다.

 

따라서 특정 범위 또는 많은 수를 판별해야 할 때는 에라토스테네스의 체를 이용해 소수를 판별한다.

에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열, 나열한 수는 전부 소수(true)라고 가정
2. 현재 숫자가 소수인지 확인
3. 소수(true)면 자기 자신을 제외하고 구간 내 자신의 배수를 모두 제거(false)
4. 다움 숫자가 소수인지 확인하고, 소수(true)면 3번 반복 아니면(false) 다음 숫자 확인
5. 위 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

function get_primes(num) {
    const prime = [false, false, ...Array(num - 1).fill(true)];
    // 0과 1은 소수가 아니기에 미리 false로 체크
    
    for (let i = 2; i * i <= num; i += 1) {
        if (prime[i]) {
            for (let j = i * 2; j <= num; j += i) {
                prime[j] = false;
            }
        }
    }
    return prime.filter(Boolean);
}

에라토스테네스의 체는 ㄴO(n log log n)으로 빠르지만 메모리가 많이 필요하다는 단점이 있다.

 

 

참고 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4