2020년/Development
에라테스토네스의 체
위지원
2020. 4. 27. 23:59
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수(소수)를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초
ko.wikipedia.org
소수를 구하는 코드
훨씬 짧은 코드도 많은데 난 뭔가 이게 이해하기 쉬워서..
def eratos(number):
number += 1 #이렇게 하면 number로 넘겨준 수 자체도 소수인경우 출력이됨
initA = [True] * number
limitN = int((number ** 0.5)) + 1
for i in range(2,limitN):
if initA[i] == True:
for j in range(i+i, number, i):
initA[j] = False
return [i for i in range(2, number) if initA[i]==True]