[알고리즘] 효율적인 소수 구하기, 에라토스테네스의 체

소수는 1과 자기 자신만을 약수로 가지는 수를 말한다.

즉 직관적으로 이를 코드로 표현한다면,

for i in range(2, n):
	if n%i == 0:
    		return False
    return True

단순히 2부터 n-1까지 순회하며 나눠지는 수가 있다면 소수가 아니라고 판단하면 된다.

하지만 이는 n까지 모두 순회하므로 O(n)의 시간복잡도를 가진다. 만약 n이 엄청 커진다면? 시간초과가 날 확률이 높다.

 

그렇다면 효율적인 소수를 구하려면 어떤 방식을 사용해야 할까?

우선 약수의 특성을 확인해야 한다.

예를 들어 16의 약수를 확인해보면, [1, 2, 4, 8, 16] 를 얻을 수 있다.

15의 약수는 [1, 3, 5, 15] 를 얻을 수 있다.

즉 가운데의 수를 기준으로 대칭적인 모습을 보이는데, 가운데의 수는 √n 으로 값을 얻을 수 있다.

즉 어떤 수 n에 대하여, √n까지만 검사를 하면 뒤의 수들은 자동으로 검사가 된다는 것을 의미한다.

O(n)의 시간복잡도를 O( √n)까지 줄일 수 있는 것!

 

이를 코드로 정리하자면,

end_num = int(n ** (0.5))
for i in range(2, end_num + 1):
	if n%i == 0:
    		return False
    return True

의 형태를 띄게 된다.

 

에라스토테네스의 체는 다량의 소수를 구할 때 효율적인데, N 이하의 수 중 모든 소수를 출력하라는 문제가 있다면 다음과 같은 방식으로 코드를 작성하면 된다.

M, N = map(int, input().split())
store = []

def arasto(n):
    end_num = int(n ** (1/2))
    if n == 1:
        return False
    for j in range(2, end_num+1):
        if n % j == 0:
            return False
    store.append(n)
    return True


for i in range(M, N+1):
    arasto(i)

print(*store)

이런 방식으로 코드를 작성하면, M과 N 사이의 모든 소수를 출력할 수 있다.