이게뭐야?
위키피디아
쉽게 말하면, 소수를 찾는 방법이다. 소수라 함은 그 수의 약수가 1과 자기 자신만을 가지는거다.
파이썬 구현
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
n = n + 1 # 이렇게 하면 소수목록에서 조회할때 -1 안해줘도 된다
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i]: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return sieve
어따씀?