728x90
반응형
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.
에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.
이 방법은 마치 체로 치듯이 수를 걸러낸다.
코드:
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
m = int(n ** 0.5) # 제곱근
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]
소수 목록 산출은 컴프리핸션을 이용한 풀이다.
2부터 n까지 for 문을 돌리는데 sieve[i]가 True 면 리스트로 만들고 전부 숫자로 만들어 리턴
다른 방법으로는
a = [False,False] + [True*(n-1)]
for i in range(2, int(n**0.5)+1):
a[i*2::i] = [False]*((n-i)//i)
cf) 2,3,5,7 만 쓰면 소수를 구할 수 있다.
출처:
반응형
댓글