소수를 찾는 알고리즘이다.
알아두면 알고리즘 문제를 풀 때 간간이 쓸모 있게 쓰이므로 숙지하도록 하자!!

출처: 위키백과: 에라토스테네스의 체
소수를 구하고자 하는 구간의 모든 수를 2부터 나열한다.
2는 소수이므로 소수 리스트에 추가한다.
자기 자신을 제외한 2의 배수를 모두 지운다. (빨간색)
남아있는 수 가운데 3은 소수이므로 소수리스트에 추가한다.
자기 자신을 제외한 3의 배수를 모두 지운다. (연두색)
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
자기 자신을 제외한 5의 배수를 모두 지운다. (파란색)
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
자기 자신을 제외한 7의 배수를 모두 지운다. (노란색)
위의 과정을 재귀적으로 반복한다.
그림의 경우, 11^2 >120 므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다
def prime_list_ver1(n):
# 리스트 초기화 (전부 소수로 간주)
sieve = [True] * (n+1)
# n의 최대약수가 sqrt(n) 이하이므로 i = sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m+1):
if sieve[i] == True: # i 가 소수인 경우
# i 이후의 i의 배수를 모두 False로 판정
for j in range(i+i, n+1, i):
sieve[j] = False
return [i for i in range(2, n+1) if sieve[i] == True]
def prime_list_ver2(n):
★1. 소수 구하기 문제는 " 구하고자 하는 수의 제곱근 < n (소수) " 가 포인트!
그 소수 n까지의 배수만 지워주면 된다.
★2. 구하고자 하는 수를 전부 소수로(True) 가정하고 소수에 배수에 해당할 경우 False로 바꿔주기
3. True 인 친구들 전부 리스트로 뽑아주면 끝!