[JS] 소수 구하기

✨ 소수

1 또는 자기 자신만을 약수로 가지는 수를 의미

즉, 1과 자기 자신 외에는 그 어떤 값으로도 나눠질 수 없다.

 

 

✨ 소수 구하는 방법

1. 가장 직관적인 방법

2부터 N-1까지 루프를 돌며 나눠보기

10 하나가 소수인지 확인하기 위해 2~9까지 하나하나씩 나눠봄.

시간 복잡도 O(n)

// O(n)
function isPrime(num) {
  for(let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

 

2. 효율성 개선하기

위의 알고리즘을 좀 더 효율적으로 개선해 보자.

그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 점을 이용.

17이 소수인지 알아보기 위해 2~4까지의 값만 루프를 돌려볼 수 있다.

 

시간 복잡도 O(sqrt(n))

// O(sqrt(n))
function isPrime(num) {
  for(let i = 2; i * i <= num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

코드는 위와 큰 차이가 없으나 이전 방법보다 더 효율적이다.

 

 

3. 에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법

예시) 2~54 범위에서 소수 찾기

먼저 앞에서부터 숫자를 확인한다. 체크하지 않은 숫자를 선택하게 되는데, 아직 어떠한 값도 체크되지 않았으므로 가장 앞에 있는 2를 선택한다. 그 후 2의 배수가 되는 값을 모두 체크해 준다.
이번에는 3을 선택한다. 이어서 3의 배수가 되는 값들을 모두 체크해 준다.
4는 이미 체크가 되었기 때문에 건너뛰고 5를 선택한다. 이미 체크된 값들은 건너뛰고 5의 배수들을 체크해 준다.
이번엔 7을 선택한다. 체크할 수 있는 수인 49를 체크하고 종료한다.
소수는 n의 제곱근보다 큰수로는 나눠지지 않는다는 점을 이용하여 8부터는 확인하지 않아도 된다. 이후 2~54까지 중 체크되지 않은 숫자는 모두 소수로 판단하면 된다.

// O(n log n)
function getPrimes(num) {
  const prime = [false, false, ...Array(num - 1).fill(true)];
  
  for(let i = 2; i * i <= num; i++) {
    if (prime[i]) {
      for(let j = i * 2; j <= num; j += i) {
        prime[j] = false;
      }
    }
  }
  
  return prime.filter(Boolean);
}

 

소수 구하기 알고리즘이 종종 나오니 외워두도록하자!

 

 

---

문제 예시

https://lazyhysong.tistory.com/entry/JS-%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0

[JS] 소수찾기