에라토스테네스의 체

📌 에라토스테네스의 체

에라토스테네스의 체는 소수를 판별하는 가장 대표적인 알고리즘이다.

소수란?

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.
예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

에라토스테네스의 체를 사용하지 않고 간단하게 소수를 판별할 수도 있다.

👀 Expamle 1

• 두 정수가 주어질 때, 두 정수 사이의 숫자 중 소수인 수만 구하기

let result = [];
function isPrime(n) {
	if(n === 1) return false; // 1은 소수가 아니다.
	for(let i = 2; i < n; i++) {
		if(n % i === 0) return false;
	}
	return true;
}

function solution(num1, num2) {
	for(let j = num1; j <= num2; j++) {
		if(isPrime(j)) {
			result.push(j)
		}
	}	
	return result;
}

solution(2, 10) // [2, 3, 5, 7]

위의 경우 시간 복잡도는 O(N)이다. 모든 경우의 수를 다 돌며 약수 여부를 확인하기 때문에 비효율적이다. 여기서 조금 더 최적화를 한다면 제곱근을 이용할 수 있다.

예를들어, 8의 경우 2 * 4 = 4 * 2 와 같은 식으로 대칭이 되기 때문에 특정 숫자의 제곱급까지만 약수의 여부를 검증하면 시간 복잡도를 O(N/2)로 최적화시킬 수 있다.

let result = [];
function isPrime(n) {
	if(n === 1) return false; // 1은 소수가 아니다.
	for(let i = 2; i<=Math.sqrt(n); i++) {
		if(n % i === 0) return false;
	}
	return true;
}

function solution(num1, num2) {
	for(let j = num1; j <= num2; j++) {
		if(isPrime(j)) {
			result.push(j)
		}
	}	
	return result;
}

solution(2, 10) // [2, 3, 5, 7]

하지만 이 방식도 대량의 소수를 한꺼번에 판별하고자 할 경우에는 비효율적이다. 이때 적용해볼 수 있는 알고리즘이 바로 에라토스테네스의 체이다.

👉 에라토스테네스의 체의 원리

• 120까지의 수가 있다는 가정 하에, 2의 배수를 지운다. 이때 자기 자신은 지우지 않는다.
• 3의 배수, 4의 배수도 자기 자신을 제외하고 지운다.
• 이런식으로 배수를 지우다 보면 최후에 남은 숫자들이 소수다.
• 이 방법의 시간복잡도는 O(N log(logN))이다.

function solution(n) {
    // idx 0, 1은 false / 나머지는 true인 길이가 n(idx : 0 ~ n)인 배열 생성
    let arr = Array(n+1).fill(true).fill(false, 0, 2)
    for(let i = 2; i <= Math.sqrt(n); i++) {
        if(arr[i]) {
            // i의 배수 false로 변경
            for(let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    return arr; // [false, false, true, true, false, true, false, true, false, false, false]
}

solution(10)

위 로직을 활용하여 소수 구하기 유형에 활용할 수 있다.

let isPrimes = solution(10);

//소수의 개수 구하기
isPrimes.filter(el => el).length; // 4

// 소수 반환하기
isPrimes.map((v, i) => v ? i : 0).filter(el => el); // [2, 3, 5, 7]