정수론 - 소수

소수(Prime Number)란

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

주의해야 할 것은 1은 소수가 아니며, 흔히 짝수라서 소수가 아닐꺼라고 생각할 수도(?) 있지만 2는 소수이다. 

구현

소수에 관한 문제는 2가지로 생각해 볼 수 있다. 

1) 특정 수(n)가 소수인지/아닌지 판별해야 할 경우

이때는 n의 약수 가 1과 자기 자신(n) 뿐이면 소수, 아니면 소수가 아니라는 정의를 이용하는게 좋다. 

다시 말해, 1~n 중 1, n을 제외한 2~(n-1) 중에서 하나라도 나누어 떨어지는 것이 있으면 소수가 아니다. / 하나도 나누어 떨어지지 않으면 소수이다. 

로 판단 할 수 있는 것이다. 

 

※ 하지만 그냥 2~(n-1)을 모두 탐색하면서 검사하려면 시간복잡도가 O(n)으로 너무 크다.. 고 생각된다. 이를 줄일 수 있는 방법은, 

sqrt(n) 까지만 검사하는 것이다. 

왜일까?? 

어떤 수 n을 24로 예시를 들어서 24의 약수를 보자. 1, 2, 3, 4,|| 6, 8, 12, 24처럼 된다. 다시말해 n을 나누는 모든 숫자 || 왼쪽에 있는 a들은 그에 대한 보수 || 오른쪽에 있는 b가 반드시 존재한다. (b : (a*b=n))

그래서 만일 a < sqrt(n) 이라면 b > sqrt(n) 이다. (sqrt(n)^2 = n) 이고, 

그렇기 때문에 || 왼쪽에 있는 a들로 나누어 떨어진다는 소리는 || 오른쪽에 있는 b들로 당연히 나누어 떨어지게되고, 그래서 a 이상 검사할 필요가 없다. !

 

var primeTester = function (n) {
  if (typeof n !== 'number' || n < 1 || n % 1 !== 0 || n === 1) {
    // n isn't a number or n is less than 1 or n is not an integer
    return false
  }
  
  for (let i = 2; i <= Math.sqrt(n); i++) {
    //그냥 i=2~<n까지하면 시간복잡도가 너무 커진다.
    if (n % i === 0) {
      return false
    }
  }
  return true
}

 

2) 어떤 수 (start num)부터 어떤 수(end num) 까지의 수 중에 소수를 모두 골라야 할 경우

이 때 위의 1번 방식을 이용해서 start num 부터 end num 을 하나하나 다 검사하면 시간 복잡도가 O(n^2)이 된다. 

그러나 에라토스테네스의 체를 이용하면 O(n log log n)의 시간 복잡도로 소수에 해당하는 수만 모을 수 있다. 

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

• step1) start num ~  end num까지의 리스트를 만든다.
• step2) 리스트의 처음 수부터 소수인지 아닌지 판별한다.
  • 소수이면 => 이것의 배수는 소수가 될 수 없다. 그래서 모두 삭제
  • 소수가 아니면 => 그것만 삭제
• step3) step2를 리스트의 마지막 숫자를 검사할 때까지 계속한다. 

출처: 위키피디아 <에라토스테네스의 체>

// 에라토스테네스의 체를 이용하여 2~n까지 소수 갯수 구하기
let solution = (n) => {
    let arr = Array(n+1).fill(true).fill(false, 0, 2);

    for(let i=2; i*i<=n; i++){
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i){
                arr[j] = false;
            }
        }
    }

    return arr.filter(e => e).length;
}

또는 

문제가 아래와 같을 때, 

Extra credit: Write a function that generates a list of all prime numbers

in a user-specified range (inclusive). If you're not quite sure where to start,

check out the Sieve of Eratosthenes on Wikipedia. (And if you're feeling

saucy, check out the Sieve of Atkin.)

코드는

//소수문제풀 때 항상 조심해야하는 두 수: 1은 소수가 아니다. 2는 소수이다.
//다 소수(true)라고 치고, 소수가 아닌 것(false)을 제외시켜 나간다.

var primeSieve = function (start, end) {
  let Era = []; //start부터 end까지의 수가 차례대로 들어가있는 배열
  for (let i = start; i <= end; i++) {
    Era.push(i);
  } //끝까지 Era 배열에 남아있는수가 소수들이다.
  if (start === 1) {
    Era.splice(0, 1);
  } //1은 소수가 아니고 모두가 다 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 (primeTester(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);
    }
  }
  //남은게 소수들로 구성된 배열
  return Era;
};

 

 

reference

coding-factory.tistory.com/600