정수론 - 소수(에라토스테네스의 체)

소수란, 약수가 1과 자기자신 뿐인 수이다. 

1은 소수가 아니며, 2는 소수이다. 2의 약수는 1과 자기자신인 2뿐이기 때문이다.

소수의 개념에 대해 자주 등장하는 알고리즘 문제

 

1) 특정 수가 소수인지 아닌 지 판별

 : 1 ~ n 사이를 for문으로 돌면서, 하나라도 n을 나누어떨어지게 하는 즉 약수가 있다면 해당 수(n)은 소수가 아니다.

 

하지만 실제로 1~n 사이를 모두 for문으로 돌면 시간복잡도가 O(n)이다. 좀 더 줄일 수 있는 방법은 없을까?
sqrt(n) 즉 n의 제곱근 수까지만 반복문을 도는 것이다.

왜????

가령 64라는 수를 가정해보자. 실제로 64는 소수가 아니다. 64를 구성하는 약수의 구성을 살펴보면

1x64 , 2x32 , 4x16, 8x8  =>  1,2,4,|8|,16,32,64 

위의 형태로 약수가 구성되어 있다. 

즉 n의 제곱근을 중심으로 더 작은수 X 더 큰 수로 만들어진게 n이라는 숫자인 것이다. 

따라서 n의 제곱근보다 작은 수 중에서 약수가 없다면 제곱근 중에서 더 큰수 두개끼리 N의 약수가 될 수 없는 것이다.

 

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

 

 

2) n ~ m 사이의 수 중에서 소수를 골라야 하는 경우. 

 : 이런 경우에는 1)번의 방법을 쓰면, 두 수 사이의 모든 수들을 반복문을 통해 점검해 주어야 하므로 시간 복잡도가 올라간다.

이 때 활용되는 것이 에라토스테네스의 체이다. (시간 복잡도 : n log logn)

에라토스테네스의 체는 소수가 아닌 수들은 반드시 다른 소수로 나누어 진다는 사실에 기반한다. 

a. n ~ m 사이의 수들로 배열을 만든다
b. 해당 배열을 반복문을 돌면서, 해당 수가 소수라면 -> 이것의 배수는 소수가 될 수 없으므로 모두 삭제
    소수가 아니라면 -> 해당 수만 삭제
c. 배열의 마지막 수까지 반복

 

var primeSieve = function (start, end) {
  let Era = [];
  for (let i = start; i <= end; i++) {
    Era.push(i);
  }
  if (start === 1) {
    Era.splice(0, 1);
  }
 
  // 에라토스테네스의 체 시작
 
  let inx = 0;
  let len = Era.length;
 
  for (let i = 0; i < len; i++) {
    let curr = Era[inx];
 
    if (curr === undefined) { //여기 중요
      return Era;
    }
 
    // console.log(Era, curr)
    if (primeNumber(curr)) {
      // 소수이면 그것만 놔두고
      for (let mul = 2 * curr; mul <= end; mul += curr) {
        // 그것의 배수는 다 제거
        if (Era.includes(mul)) {
          Era.splice(Era.indexOf(mul), 1);
        }
      }
      inx++;
    } else {
      // 소수 아니면 제거
      Era.splice(Era.indexOf(curr), 1); // start 이전의 값은 제외 처리를 해 주지 않으므로, 이 코드가 필요하다.
    }
  }
 
  // 남은게 소수들로 구성된 배열
  return Era;
};

 

-> 파이썬에서는 반복문을 종료해주는 기저조건이 조금 달라야 한다. 위와 같이 두면, index 에러가 난다.

파이썬에서의 기저 조건은 아래와 같이 해서, idx가 배열을 벗어나지 않도록 해주어야 한다.

 if idx >= len(num_list):
        break