[알고리즘] 소수 찾기 - 에라토스테네스의 체

Sjin·2021년 1월 9일

방법 1

알고리즘

소수를 담는 배열을 만든다.
2~n까지 각 수가 소수인지 확인하기 위해 만들어간 소수의 배열에서 숫자의 제곱근까지만 탐색한다.
한 번도 나누어 떨어지지 않고, 제곱근까지 탐색을 완료하면 그 수는 소수이다.
하나라도 나누어 떨어지면 그 수는 소수가 아니다.

=> n까지 탐색하는데 각각의 경우에서 다시 소수 리스트를 확인해야하므로 예상보다 시간이 오래걸린다.

코드

function solution(n) {
    let answer = 0;
    const prime = [];
    let target, targetIdx, isFail;
    for (let number = 2; number <= n; number++) {
        if (prime.length === 0) {
            prime.push(number);
            answer++;
        } else {
            target = ~~Math.sqrt(number);
            isFail = false;
            for (let i = 0; i < prime.length; i++) {
                if (!isFail && prime[i] > target) {
                    break
                } else if (!(number % prime[i])) {
                    isFail = true;
                }
            }
            if (!isFail) {
                prime.push(number);
                answer++;
            }

        }
    }
    return answer;
}

방법 2 ( 에라토스테네스의 체)

개념

체에 걸러내듯이 소수가 아닌 수들을 걸러내고 남은 수들이 소수가 된다.

구현 원리

탐색하고 싶은 수까지 체크여부를 표시할 수 있도록 배열 준비한다.
2는 체크 표시가 없으므로 소수이다. 2를 제외한 2의 배수는 소수가 아니므로 체크 표시한다.
3은 체크 표시가 없으므로 소수이다. 3을 제외한 3의 배수는 소수가 아니므로 체크 표시한다.
4는 체크 표시가 있으므로 소수가 아니다. 건너뛴다.
5는 체크 표시가 없으므로 소수이다. 5를 제외한 5의 배수는 소수가 아니므로 체크 표시한다.
위의 과정을 n까지 반복하면 된다. n이 어떤 수의 배수인지 확인하기 위해서는 n의 제곱근까지만 확인하면 된다. 따라서 n의 제곱근의 배수까지만 살펴보면 n까지 소수 여부를 판별할 수 있다.

알고리즘

n까지 탐색하고 싶으면 n+1 크기의 배열을 준비한다.
2부터 n까지 탐색 시작
- 체크가 안되있다면 소수이므로 건너뛴다.
- 체크가 되있다면 해당 수를 제외한 배수를 인덱스로 가지는 곳에 체크한다.
체크가 안되있는 수들이 소수이다.

코드

function solution(n) {
    let visited = new Array(n + 1).fill(0)
    const target = ~~Math.sqrt(n);
    for (let num = 2; num <= target; num++) {
        if (visited[num]) {
            continue;
        } else {
            for (let i = num * 2; i <= n; i += num) {
                visited[i] = 1;
            }
        }
    }
    return visited.filter(function (value, idx) {
        if (idx >= 2 && visited[idx] === 0) {
            return true;
        }
    }).length;
}