[알고리즘] 소수 판별식 (에라토스테네스의 체)

1. num 사이의 숫자를 모두 나눠서 확인하는 방법

function isPrime(num) {
  for(let i = 2; num > i; i++) {
  if(num % i === 0) {
    return false;
   }
  }
 return num > 1;
}

 

 

2. num 제곱근 까지만 확인 하는 방법

function isPrime(num) {
  let sqrt = parseInt(Math.sqrt(num)); // num에 제곱근 후 소수점 버림

  if (num === 1) {
    return false;
  }

  if (num === 2) {
    return true;
  }

  if (num % 2 === 0) {  
    return false;
  }
  
  // 1, 2에 대한 경우의 수와 2의 배수는 미리 걸러냄

  for (let i = 3; i <= sqrt; i += 2) {
    if (num % i === 0) {
      return false;
    }
  }

  return true;
}

 

에라토스테네스의 체

1을 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리입니다.

 

코드스테이츠에서 섹션 1에서 진행을 하였을 때 에라토스테네스의 체를 찾아보라는 말을 했었는데 왜? 이 코드랑 그렇게 관련이 있나 싶었는데 에라토스테네스의 체의 원리가 해당이 되지만 중요한 점은 n까지 전부 검사하지 않아도 √n까지만 검사해도 결과는 같다. 라는 점이 필요했습니다.

 

예를 들어 13이라고 했을 때 그 사이에 있는 수인 3과 9로만 예를 들면

9는 3의 배수이기 때문에 3에서 검사를 했을 때 나누어 떨어지지 않는다면 9로 나누어 볼 필요가 없다는 이야기입니다.

그렇기 때문에 √13 은  약 3.xxx 의 값이고 3까지만 검사를 해보면 답은 나온다는 것입니다.

 

이 수학적인 내용이 코드를 더욱 빠르게 합니다. 최근에 배운 시간복잡도에 대한 생각을 적어 보자면

1번 방식은 시간복잡도가 O(n)인 반면에

2번 방식은 시간복잡도가 O(log n) 의 효율을 보여줍니다.

빠르기로는 O(log n) > O(n) 이며 n이 커지면 커질수록 효율차이는 벌어지게 됩니다.

 

 

처음에는 왜 굳이 저렇게 복잡한 방식을 써야하나? 요즘 컴퓨터 엄청 빠른데 금방 연산 하지 않나? 생각이 들었지만 시간복잡도를 배우고 나서 코드를 보는 시각을 달리 할 수 있었습니다.

지금은 그냥 가벼운 소수 구하기에 그치겠지만 더 큰 데이터를 다루게 된다면 이야기는 달라지게 될 것 같습니다.