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

방법 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;
}

참고

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