주요 내용
에라토스테네스의 체
에라토스테네스의 체로 소수의 목록을 만들 수 있습니다. 만든 이: Brit Cruise
대화에 참여하고 싶으신가요?
- 65는 소수가 아닌 합성수 아닌가요?에 파란색으로 표시돼있는데... 2:53
Isn't 65 a composite number, since it's 1*5*13? Why is it marked as a prime number (blue) at? 2:53(추천 1 번)
동영상 대본
지금부터 고대로부터 내려오는 유한수 N보다 작은 소수를
나열하는 방법인 에라토스테네스의 체에 대해서
이야기해보겠습니다 에라토스테네스는
기원전 276년에 태어났습니다 그러니까 이 방법은
약 2200년정도 전에 나온거네요 하지만 매우 우아하고 간단해서 아이에게도
쉽게 가르칠 수 있어요 그럼 예를 하나 들어봅시다 100까지의 모든 소수를
계산하고 싶다면 만약 만 또는 10억까지
구하기를 원한다 하더라도 똑같은 방식으로 계산할 겁니다 우선 모든 숫자에 아무런
표시를 하지 않았다고 가정합시다 회색은 아무런 표시가
되지 않았다는 뜻입니다 처음에 1 부터 시작해서 아무런 표시가 되지 않은
수를 만나면 소수입니다 바로 2를 만나고 소수라고 말할 수 있어요
어떤 표시도 없으니까요 두 번째 단계로 2의 배수를 모두 제거합니다 왜냐하면 전부 합성수 이니까요 이렇게 모든 2의 배수를 지울겁니다 빨간색은 합성수입니다 이제 반복합니다 다음은 3으로 넘어가게 되겠네요 3은 아무런 표시가 없으므로
3도 소수입니다 이젠 3의 배수도 지울 수 있습니다 간단한 최적화 방법이 있어요 6은 이미 지워졌습니다 우리는 배수를 지우는 것을 그 숫자의 제곱에서부터
시작하면 간단합니다 그러므로 3의 3배는 9가되고 9부터 시작하여 모든 3의 배수를 합성수라고
표시할 수 있습니다 그러고 나서 다시 돌아가면
4는 건너 뛰어도 되겠네요 4는 이미 표시가 되어있습니다
합성수라는 뜻이죠 다음 5로 넘어가면
아무런 표시가 없으므로 5도 역시 소수입니다 그럼 5에 5배한 값은 25이고 25로가서 25, 30, 35, 40, 45과 같이
5의 배수에 표시를 합니다 전부 합성수입니다 계속해서 7을 만날때까지 계속합시다 7은 아무런 표시가 되어 있지
않으므로 7은 소수입니다 그리고 7의 7배는 49이므로 49부터 시작하여 모든
7의 배수를 합성수라고 표시할게요 다음으로 표시가 안된 11까지 갑시다
11은 소수입니다 11의 11배는
100보다 큰 수입니다 그러므로 이 지점에서
멈출 수 있습니다 사실 10에서
멈출 수도 있었어요 왜냐하면 이제 남아있는
표시되지 않은 수는 전부 소수일 테니까요 그러면 남은 모든 수를 전부
소수라고 표시할 수 있습니다 이게 알고리즘의 전부입니다
매우 간단하지요 그리고 우리가 어떤일을 해야하는지
간단하게 일반화해서 어떠한 숫자 N까지의 모든 소수를 찾는 일종의 체 처럼 작동하는
프로그램을 만들 수 있습니다 먼저 주요 반복문을
만들어보겠습니다 "2부터 N의 제곱근까지의
모든 수 a에 대해" "2부터 N의 제곱근까지의
모든 수 a에 대해" 여기서 알 수 있듯이
10을 만났을때 멈춰야 합니다 방금전에 저는 11까지 셋지만 남은 모든 수가 소수이므로 멈춰야 합니다 그러므로 2에서부터 N의 제곱근까지 다음과 같은 절차를 따를 겁니다
만일 a에 아무런 표시가 되어 있지 않다면 a는 소수라는 것을 알 수 있고
소수를 찾게 된다면 a의 모든 배수들에 대해서
합성수라고 표시를 합니다 이게 끝입니다 그렇게 소수를 찾고
그 배수들에 대해서 표시를 하고 난 다음에는 다시 a보다 1 큰 값으로
돌아가서 다시 시작합니다 2에서 시작하고
다음에 3으로 가고 마찬가지로 4, 5로 갑니다 다 마치고 나면
모든 소수를 구할 수 있습니다 이 또한 반복문으로 이루어져 있습니다 소수를 찾는 주반복문도 있고 또한 그 배수를 지우는
반복문도 있습니다 여기서 중요한 점은 반복문 안에
또 다른 반복문이 있다는 것입니다 반복문 안에
또 다른 반복문이 있다는 것입니다 한 예시로 이 알고리즘으로
프로그램을 만들었습니다 JavaScript로 작성했습니다 만약 100을 넣는다면
그 이하의 모든 소수가 나올 것이고 200을 넣는다면
그 이하의 모든 소수가 850을 넣는다면
850 이하의 모든 소수가 나올 것입니다 이 아래에는 프로그램을 만들
당시의 기록을 첨부하고 어떻게 만들었는지 설명해 놓았습니다