Note: 소수 판별

[YimJiYoung]

소수: 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수

# 소수 판별 함수
def is_prime(x):
  # 2부터 x의 제곱근까지의 모든 수를 확인하여
  for i in range(2,  int(math.sqrt(x)) + 1):
    # x가 해당 수로 나누어떨어진다면
     if x % i == 0:
          return False # 소수가 아님
  return True

에라토스테네스의 체

1. 2부터 N까지의 모든 자연수 나열
2. 남은 수 중에서 아직 처리하지 않는 가장 작은 수 i 찾기
3. 남은 수 중에서 i의 배수 모두 제거
4. 더 이상 반복할 수 없을 때까지 2, 3번 과정 반복

// 에라토스테네스의 체
  const isPrime = new Array(maxNum).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(maxNum); i++) {
    if (isPrime[i]) {
      let j = 2;
      while (i * j <= maxNum) {
        isPrime[i * j++] = false;
      }
    }
  }