에라토스테네스의 체를 이용한 소수 찾기

- 해당하는 모든 소수를 출력하라.

소수란 1과 자기 자신만을 약수로 가지는 수이다. 100이하의 자연수 중 모든 소수를 출력하시오.

소수를 오름차순으로 출력한다. 각 출력값 사이는 공백으로 구분하고 출력값 5개 마다 줄바꿈을 한다.

아래와 같은 결과 값이 출력되어야 한다.

2 3 5 7 11 
13 17 19 23 29 
31 37 41 43 47 
53 59 61 67 71 
73 79 83 89 97

 

위 내용까지 트라이캐치의 소수 찾기 문제이며, 아래코드는 오름차순과 출력값 사이를 공백으로 구분하고, 5개마다 줄바꿈을 적용하지 않은 소스이다.

 

해당 코드는 범용성을 위해 자바스크립트를 이용하여 만들었으며, 에라토스테네스의 체를 이용한 방법이다.

function getPrimesUpTo(n) {
    if (n < 2) return [];

    // true는 소수로 간주되는 초기 상태
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // i의 배수들을 모두 false 처리
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 인덱스가 true인 숫자만 필터링하여 소수 목록 생성
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push(i);
    }

    return primes;
}

// 예시 사용
console.log(getPrimesUpTo(100)); // 100 이하의 모든 소수 출력

 

 

아래는 재귀 함수를 이용하여 좀더 간략하게 구성

function sieve(arr, primes) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] % primes[0] === 0 && arr[i] !== primes[0]) {
            arr.splice(i, 1);
            i--; // 중요: 삭제 후 인덱스 조정
        }
    }
    primes.shift();
    if (primes.length === 0) arr.shift(); // 1 제거

    return primes.length === 0 ? arr : sieve(arr, primes);
}

const numbers = Array.from({ length: 100 }, (_, i) => i + 1);
const primesToUse = [2, 3, 5, 7]; // 100 이하라면 sqrt(100) 이하 소수만 필요
console.log(sieve(numbers, [...primesToUse]));

 

 

에라토스테네스의 체에 대한 부연설명

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

아래 움직이는 이미지를 통해 쉽게 알고리즘을 눈으로 확인하자.