위키백과

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

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
101번째 줄:
 
 
◆ python(3.6.4)으로 구현<ref>{{웹 인용|url=http://code.jasonbhill.com/sage/project-euler-problem-10/|제목=Project Euler Problem 10 {{!}} Jason's Code Blog|언어=en-US|확인날짜=2018-03-13}}</ref>
◆ Python(3.6.4)을 현구
<source lang="python3">
def prime_sum(n):
 
primes = [True] * n
num=1000 # 초기값을 설정한다.
primes[0], primes[1] = [None] * 2
from cmath import sqrt # 루트식을 사용할 수 있는 함수를 탑재한다. 이유는 추후에 설명할 것이다.
sum = 0
factor =3 # 삭제할 배수의 초기값을 설정한다. 짝수는 2의 배수를 삭제할 때 제거될 것이므로 생략한다.
for ind, val in enumerate(primes):
limit = sqrt(num).real # 초기값의 제곱근까지 나눠보면 답이 나오므로 나눌 값에 대해 제한을 건다. '.real'는 허수부분을 버린다는 뜻이다.
if val is True and ind > n ** 0.5 + 1:
candidates = [2*a-1 for a in range(2, num + 1)] # 후보군을 설정한다. 짝수는 모두 2의 배수이므로 효율을 높이기 위해 생략한다.
sum += ind
 
elif val is True:
while factor <= limit:
primes[ind * 2::ind] = [False] * (((n - 1) // ind) - 1)
for number in candidates:
if number % factor =sum += 0:ind
print(sum)
if number != factor:
candidates.remove(number) # 모든 후보군에 대해서 factor로 나눠서 나머지가 0이 되면 그 수를 삭제한다.이 때 factor가 소수라면 제외한다.
 
factor += 2 # factor를 증가시킨 후, factor가 제한을 넘지 않으면 다시 반복한다.
 
candidates.append(2) # 생략한 2를 추가한다
print(candidates) # 결과값 출력
 
 
</source>
원본 주소 "https://ko.wikipedia.org/wiki/에라토스테네스의_체"