본문바로가기
[오일러 프로젝트] 블랙 위도우: 200만 이하 소수의 합은 얼마일까?
수학동아 2020.03.26 14:02

 

코.알.못 홍 기자의 코딩 도전기

코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갈 예정입니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 파이썬 모두 정복할 수 있지 않을까요?

 

 

‘어벤져스: 엔드게임’에서 생을 마감해 아쉬웠던 블랙 위도우가 영화 ‘블랙 위도우’로 돌아올 예정이죠.

그런데 표지에서 본 블랙 위도우와 다르게 제 모습은 어딘가 위축돼 보인다고요?

블랙 위도우는 어떤 전투에서도 이길 수 있을 것처럼 당당하지만 전…, 그렇지 않다고요!

과연 제가 블랙 위도우처럼 소수라는 전쟁터에서 살아남을 수 있을까요?

 

 

<오일러 프로젝트 10번 문제>

10 이하의 소수를 모두 더하면 2+3+5+7=17입니다.

200만 이하 소수의 합은 얼마일까요?

 

 

드디어 등장했습니다. 수학계의 타노스 급 문제, 소수입니다. 소수는 1과 자기 자신만을 약수로 가지는 수로 많은 수학자가 소수를 찾는 것에 집중했죠. 그중 고대 그리스의 수학자 에라토스테네스는 소수만 찾을 수 있는 '에라토스테네스의 체'를 고안해내기도 했습니다.

 

 

이번 오일러 프로젝트 10번 문제는 에라토스테네스의 체를 코딩으로 구현해 풀어볼 거예요.

200만 이하의 소수를 찾아 그 합을 구해볼까요?

 

 

파이썬 완전정복! 필수 명령어

 

1. 200만 개의 숫자를 리스트(List)로 나타내기

자동으로 순서가 있는 집합을 만드는 ‘리스트(List) 표기법’을 사용해 수를 나열합니다. 즉 대괄호([])로 리스트라는 걸 표시해 True1, True2, True3처럼 0번부터 200만 번까지 번호가 붙은 True 200만 1개를 리스트 p로 정의합니다.

 

 

2. 이중 반복문으로 합성수를 걸러 소수만 얻기

1월호 오일러 프로젝트에서 다뤘던 ‘for 문’과 ‘range 함수’를 이용해 소수만 남겨 봅시다. 0과 1은 소수도 합성수도 아니므로 True 0, True1은 소수가 아니라는 뜻의 False로 표기하고, True2에서 시작합니다. 에라토스테네스의 체에서 2의 배수부터 지웠던 것처럼, 먼저 False로 바뀌지 않은 가장 작은 i번째 True를 찾습니다.

 

 

i번째 True는 그대로 두고, i의 배수를 번호로 갖는 True를 모두 False로 바꿉니다. 즉 2i번째부터 3i, 4i 등 i 간격으로 모든 True를 False로 바꾸도록 range(시작 번호, 끝 번호+1, 간격) 형태로 코드를 입력합니다.

 

 

두 가지 반복문을 차례대로 실행하면 소수 번호에만 True로 표시됩니다.

 

 

TIP1. 파이썬은 순서를 매길 때 0번부터 시작합니다. 따라서 200만까지 다루기 위해서는 200만 1개의 True를 만들어야 합니다.

 

TIP2. 수많은 자연수에서 소수만 골라낼 때 쓰는 반복문 2개가 같은 듯 다르죠? 등호 1개(=)는 오른쪽 항의 값을 왼쪽 변수에 대입하라는 것, 등호 2개(==)는 양쪽이 같다는 뜻임을 잊지마세요! for 문과 if 문을 마치면서 마침표(:)를 넣는 것도요!

 

 

도전! 오일러 프로젝트 10번 문제 뽀개기

* 코딩 언어는 Python으로 두고 실행하세요!

 

 

#1 200만 1개의 True를 순서대로 나열한 리스트 p를 만듭니다.

#2 소수가 아닌 0과 1번의 True는 미리 False로 바꿉니다.

#3, 4, 5, 6  에라토스테네스의 체 원리로 소수 번째의 True만 남기고 모두 False로 바꿉니다.

#7 구해야 하는 소수의 합을 변수 sum으로 정의하고 초깃값으로 0을 입력합니다.

#8, 9 리스트 p에서 i번째 수가 True라면 i를 sum에 더합니다.

#10 True의 수를 모두 더한 sum을 출력합니다.

 

 

Bonus! 오일러 퀴즈

오일러 프로젝트 10번 문제를 위 코딩창에서 풀어보고, 다음 예제 문제에도 도전해 보세요!

 

1. 300만 이하 소수의 합을 구해보자.

Hint. 곳곳에 있는 ‘2000001’을 다른 숫자로 바꿔보세요!

2. 200만 이하 합성수의 합을 구해보자.

Hint. ‘if p[i] == True: sum = sum + i’의 조건을 바꿔보세요!

 

 

이번 문제를 풀 때 2를 제외한 짝수는 모두 소수가 아니니까

짝수를 빼면 더 빨리 계산 결과를 얻을 수 있지 않을까요?

아래의 계산 시간을 재는 명령어를 사용해 차이를 비교해보세요!

 

 

 

참고로 저의 최고 기록은 0.92초였답니다! (지금은 1.5초정도 나오네요. 왜 다르죠???)

저보다 더 빨리 소수의 합을 구했다면 댓글을 남겨 알려주세요!

그리고 다음 달에도 소수와 관련된 문제가 또 나올 예정이니 기대해주세요~

 

첫 댓글의 주인공이 되어 보세요!
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911