개요

정수를 다루는 코딩 테스트문제도 굉장히 많다. 대표적으로 소수를 구하는 문제가 있다.
이번 기회에 정리해보려한다.

소수 구하기

소수란 자기 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 의마한다.
좀더 쉽게 말하면 1과 자기 자신을 제외한 수 외에는 약수가 존재하지 않는 수를 말한다.
예를 들어 4는 2라는 약수가 존재하니 소수가 아니고 7은 1과 자기 자신을 제외한 수로 나누었을 때 딱 떨어지지 않으니 소수에 해당한다.

그럼 만약 1부터 100까지의 수 중에 소수의 갯수를 구하는 문제가 있다면 어떻게 구할 수 있을까?

가장 먼저 생각나는 건 소수의 정의를 이용하는 것이다.
한 가지 연산을 줄일 수 있는 팁이 있는데 반복문을 돌 때 N의 제곱근이 n이라고 하면 N = a * b를 만족하는 a와 b가 모두 n보다 클 수가 없다.
예를 들어 16의 제곱근은 4로 2 * 8의 경우 2는 16의 제곱근인 4보다 작고 8은 4보다 크다. 둘 다 제곱근보다 크면 그 곱은 16을 넘어가기 때문이다. 4이하의 수만 확인하면 (1, 16), (2, 8), (4, 4)이렇게 모든 약수가 구해진다.
따라서 16이 소수인지 확인하려면 4이하의 수로 나누어 떨어지는지 확인하면 된다.

count = 0
for i in range(1, 101):
    is_prime = True
    if i == 1:
        is_prime = False
    else:
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                is_prime = False
                break

    if is_prime:
        count += 1

print(count)

시간 복잡도는 O(n^2)이 된다.

다른 방법은 없을까?

고대 그리스 수학자인 에라토스테네스에 대해 들어본 사람도 있을 것이다. 기원전에 막대기 하나로 지구의 둘레를 근사치로 계산해낸 유명한 수학자다.

에라스토테네스가 소수를 구하는 좀 더 간단한 방법도 생각해냈는데 바로 숫자들을 체로 걸러서 소수만을 남기는 방법으로 에라스토테네스의 체라고 부른다. 방법은 이렇다.

  1. 찾을 범위까지의 수를 나열한 다음, 소수가 아닌 1을 우선 지운다.
  2. 1 다음으로 큰 수인 2를 남겨두고 2의 배수를 모두 찾아서 지운다.
  3. 그다음으로 큰 수이면서 지워지지 않은 3을 남겨두고 3의 배수를 모두 지운다.
  4. 이런식으로 더 이상 지울 것이 없을 때까지 반복한다.

얘를 들어 1부터 16까지의 수에서 소수를 찾아보자.

먼저 1을 지운다. 2를 제외한 2의 배수를 모두 지운다. 그럼 1, 2, 3, 5, 7, 9, 11, 13, 15가 남는다.
이제 3을 제외한 모든 배수를 지운다. 1, 2, 3, 5, 7, 11, 13이 남는다.
다음은 4를 제외한 모든 배수를 지운다.
1, 2, 3, 5, 7, 11, 13 이렇게 끝이 났다.
총 6개의 소수가 나왔다.

코드로 나타내보자

import math
M, N = map(int, input().split())
A = [0] * (N + 1)

for i in range(2, N + 1):
  A[i] = i

for i in range(2, int(math.sqrt(N) + 1)):
  if A[i] == 0:
    continue
  for j in range(i + i, N + 1, i):
    A[j] = 0 

for i in range(M, N + 1):
  if A[i] != 0:
    print(A[i])