[알고리즘] 소수 구하기 - JavaScript

 소수 ? 

1 또는 자기 자신만을 약수로 가지는 수를 의미한다. 

 

소수를 구하는 방법 

2부터 N - 1까지 루프를 돌며 나눠보기 

소수를 구할 때 가장 먼저 생각할 수 있는 방법으로 O(n) 시간 복잡도를 가진다. 

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

다른 소수 구하는 방법에 비해 느린편에 속한다. 

 

제곱근으로 확인하기 

어떤 소수라도 N의 제곱근보다 큰 수로 나눠지지 않는다는 공식을 이용한다. 

시간 복잡도는 O(sqrt(n)) 으로 훨씬 빠른 방법이다. 

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

에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 

범위안의 숫자 중에 몇개의 소수가 있는지 알고 싶을때 자주 사용한다. 

예를 들어 30까지에서 알고 싶은 경우 

처음 2를 소수에 넣고 2의 배수를 전부 지운다. 

다음으로 3을 소수에 넣고 3의 배수를 전부 지워준다. 

4는 2의 배수라서 넘어가고 5를 소수에 넣고 5의 배수를 전부 지워준다. 

6부터는 제곱이 30보다 크기때문에 끝나서 지워진 숫자 외 모든 숫자가 소수가 된다. 

 

function get_primes(num) {
    const prime = [false, false, ...Array(num - 1).fill(true)];
    
    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);
}