[알고리즘] 에라토스테네스의 체

에라토스테네스의 체?

이름도 어렵다. 에라토스테네스의 체? 뭔 말이야? 소수를 판별하는 알고리즘이란다.
소수들을 대량으로 빠르고 정확하게 구하는 방법이다.

에라토스테네스의 체 원리

우선, 일정 범위의 숫자 배열을 리스트화 한 다음 리스트 안에서 소수를 걸러내는 것이다. 정확히는 소수가 아닌 것을 걸러내고 소수만 뽑아오는 것이다.

에라토스테네스의 체 코드

# 우선, 숫자의 범위를 정해보자. 0 ~ 1000까지.
p = 10 ** 3 
# 0 ~ 1000까지의 숫자 배열을 만들기 위해 prime을 정의한다.
# 0, 1은 소수가 아니기에 False로 할당 하였고, 2는 소수이기에 True로 할당하였다.
prime = [False, False] + [True] * (p - 1)
# 결국, prime 리스트에서 2이상 부터는 소수로 간주하고 True로 할당
# prime = [False, False, True, True, ..., True]

for i in range(1, int(p) + 1):
  if prime[i]:
    print(i)
    	# i가 소수라면, i의 배수는 소수가 아니다를 이용함.
        # ex) 3 = 소수, [6, 9, 12, 15 ... 1001] 3의 배수는 소수가 아니다. 
        # 결국, prime의 6, 9, 12, 15에 할당된 True는 False로 바뀐다. 
        # 체에 걸리지는 것이지.
    for j in range(2 * i, p + 1, i): # 6부터 1001까지 i(3)만큼 건너뛰면서 탐색
        	prime[j] = False  	

이제 소수들만 뽑아 낼 수 있다. 처음에 이해하는데 어려웠지만, 이해하고나서는 정말 빠른 속도 소수를 구할 수 있고, 여러 알고리즘 문제에도 활용할 수 있는 알고리즘 방식이었다.

reference : https://wlgustlra.tistory.com/8