위키백과

에라토스테네스의 체: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
TedBot (토론 | 기여)
봇, 업로더
2,726,677 편집
잔글 봇: 틀 이름 및 스타일 정리
102번째 줄:
 
◆ Python 으로 구현
<source lang="pythonpython3">
 
#결과 값을 저장하는 목록을 미리 생성한다.
num=1000 # 초기값을 설정한다.
result = []
from cmath import sqrt # 루트식을 사용할 수 있는 함수를 탑재한다. 이유는 추후에 설명할 것이다.
#전체 범위를 지정한다. : 1은 소수임을 알고 있으므로 제외하고 2부터 수행해야 하지만 초기값은 별도로 생성할 것이므로 3부터 999까지의 범위로 한다.
factor =3 # 삭제할 배수의 초기값을 설정한다. 짝수는 2의 배수를 삭제할 때 제거될 것이므로 생략한다.
candidates = range(3,1000)
limit = sqrt(num).real # 초기값의 제곱근까지 나눠보면 답이 나오므로 나눌 값에 대해 제한을 건다. '.real'는 소수부분을 버린다는 뜻이다.
#초기값을 설정한다.
candidates = [2*a-1 for a in range(2, num + 1)] # 후보군을 설정한다. 짝수는 모두 2의 배수이므로 효율을 높이기 위해 생략한다.
base = 2
 
#초기값의 배수를 구하기 위한 임시 변수를 생성한다.
while factor <= limit:
product = base
whilefor number in candidates:▼
if number % factor == 0:
if number != factor:
candidates.remove(number) # 모든 후보군에 대해서 factor로 나눠서 나머지가 0이 되면 그 수를 삭제한다.이 때 factor가 소수라면 제외한다.
 
factor += 2 # factor를 증가시킨 후, factor가 제한을 넘지 않으면 다시 반복한다.
 
candidates.append(2) # 생략한 2를 추가한다
print(candidates) # 결과값 출력
 
#전체 범위 내에서 "에라토스테네스의 체" 알고리즘을 수행한다.
▲ while candidates:
#임시변수가 1000미만일 때까지 다음을 수행한다.
while product < 1000:
#임시변수가 전체 범위내 존재한다면 :
if product in candidates:
#전체 범위 목록에서 임시변수를 삭제한다.
candidates.remove(product)
#임시변수는 기본값의 배수이다.
product = product+base
#결과 목록에 기본값을 추가한다.
result.append(base)
#다음 기본값은 (이미 걸러진)전체 목록의 첫 번째 값이다. : 1회 걸렀을 경우 2와 2의 배수를 모두 삭제했으므로 3이다.
base = candidates[0]
#초기값의 배수를 구하기 위해 임시 변수를 다시 생성한다.
product = base
#전체 범위에서 초기값을 제거한다.
del candidates[0]
# 범위 내의 마지막 기본값을 결과 목록에 추가한다.
result.append(base)
#결과 목록을 화면에 출력한다.
print result
 
</source>
원본 주소 "https://ko.wikipedia.org/wiki/에라토스테네스의_체"