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

00. 에라토스테네스의 체란

에라토스테네스의 체(Sieve of Eratosthenes) 란 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(prime number)를 찾는 방법으로,  마치 체로 치듯이 수를 걸러낸다고 하여 이러한 이름이 붙여졌다.  가장 대표적인 소수 판별 알고리즘으로, 2 이상 n 이하의 정수 x가 소수인지 아닌지 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘이다.

 

소수(prime number)는 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 양의 정수로 2,3,5,7,11...등의 숫자들이 소수에 속한다.

 

1부터 120 사이의 소수를 찾는 이미지

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
    그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

그림의 경우, 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

01. 소수 판별 알고리즘

1. 단순 모든 수 판별

1이 아닌 2부터 n사이의 모든 정수를 다 나누어, 조건에 일치하는 수가 있는지 확인하는 방식이다.

function isPrime(n){
    if (n<=1) return false;
    //1과 음의 정수 제외
    for (let i = 2; i < n; i++) {
        //1은 제외, 2부터 소수
        if (n % i === 0) return false;
        //나머지 유무로 소수 판별
    }
    return true;
}

2. 주어진 수의 절반만 판별

n의 약수는 n의 절반 이상이 될 수 없기 때문에 절반으로 나누어 판별하는 방식이다.

function isPrime(n){
    if (n<=1) return false;
    for (let i = 2; i < n/2; i++) {
        //n을 절반으로 나누어 판별 수를 줄임
        if (n % i === 0) return false;
    }
    return true;
}

3. 제곱근 Math.sqrt() 활용

제일 보편적으로 사용되는 방식으로, 소수를 구하고자 하는 범위 2~n이 있을 때, 2~n의 제곱근에 해당하는 범위 안의 소수의 배수들을 계속 제외하면 결국 소수만 남는 것을 활용한 방식이다.

function isPrime(n){
	if (n<=1) return false;
    for (let i = 2; i <= Math.sqrt(n) ; i++) {
        if (n % i === 0) return false;
    }
    return true;
}

 

02. 소인수 분해 알고리즘

소인수분해(prime factorization, integer factorization)는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다.

1. i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다.
2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다.
3. n이 1이 될 때까지 위 과정을 반복한다.

 

작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0가 성립하지 못하므로 n%i == 0이 성립하는 첫번째 i는 소수라는 점을 이용한 알고리즘이다.

 

//1
let result=[];
function primeFactors(n){
    for (let i=2;i<=n;i++){
        while(n%i===0){
            result=[...result,i];
            n/=i;
        }
    }
    return result;
}

console.log(primeFactors(14)) //[ 2, 7 ]

//2
function primeFactors(n){
  var factors = [], 
      divisor = 2;

  while(n>2){
    if(n % divisor == 0){
       factors.push(divisor); 
       n= n/ divisor;
    }
    else{
      divisor++;
    }     
  }
  return factors;
}

---

03. 문제 활용 예시

소수 판별 문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/120846

function solution(n) {
	//합성수를 찾는 문제
    //즉, 소수를 제외한 값을 넣기
    const isPrime = (num) => {
        for (let i = 2; i <= Math.sqrt(num) ; i++) {
            if (num % i === 0) return true;
            //소수 제외한 값을 세야 하기 때문에 true
        }
        return false;
    }

    for (let i=1;i<=n;i++){
        if (isPrime(i)) answer+=1;
    }
    
    return answer;
}

소인수 분해 문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/120852

function solution(n) {
    var answer = [];
    for (let i=2;i<=n;i++){
        while(n%i===0){
            answer=[...answer,i];
            n/=i;
        }
    }
    answer=[...new Set(answer)];
    return answer;
}

 

---

참고 자료

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

https://mine-it-record.tistory.com/509