코딩테스트를 풀다 보니 소수와 관련된 문제가 정말 많이 나와서 따로 개념을 정리해 보았다.

---

소수

1. 정의

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수를 의미한다.

1보다 큰 수 중 소수가 아닌 수는 합성수라고 한다.
> 모든 합성수는 소수들만의 곱으로 나타낼 수 있으며, 이것을 소인수분해라고 한다.

위와 같은 특징때문에 자연수 n이 소수인지 판단하기 위해서는 √n보다 작은 수들과만 비교하면 된다.
> 나눗셈을 할 때 나누는 수와 몫 중 하나는 무조건 √n보다 작기 때문이다.

2. 소수 찾기

가장 유명한 방법은 에라토스테네스의 체이다.

1. 찾고자 하는 범위의 자연수를 나열한다.
2. 1은 지운다.
3. 2부터 시작하여, 2의 배수를 지워나간다.
4. 다음 소수의 배수를 모두 지운다.

코드로 나타내면 아래와 같다.

import math

def use_eratosthenes(n):
    arr = [0, 0] + [1] * (n-1)
    for i in range(2, int(math.sqrt(n)+1)):
        if arr[i]:
            for j in range(2*i, n+1, i):
                arr[j] = 0
    return [i for i, j in enumerate(arr) if j]

단순 반복을 통해 소수를 찾을 수도 있지만 에라토스테네스의 체와 비교하면 속도에서 아주 큰 차이를 보인다.

def use_loop(n):
    arr = list(range(2, n+1))
    for i in range(2, n+1):
        for x in range(2,i):
            if i % x == 0:
                arr.remove(i)
                break
    return arr

start = time.time()
use_loop(100000)
end = time.time()
print(f"use_loop: {end - start:.5f} sec")
# use_loop: 20.98831 sec

start = time.time()
use_eratosthenes(100000)
end = time.time()
print(f"use_eratosthenes: {end - start:.5f} sec")
# use_eratosthenes: 0.00926 sec

---

참조:
위키백과 - 소수
위키백과 - 합성수