[수학 때려 잡기 시리즈 (7)] 에라토스테네스의 체

에라토스테네스의 체를 이용해 소수를 찾는 방법을 소개하려고 해.

우선 1부터 50까지 숫자를 적어볼까?

보통 100까지 하는 경우가 많은데 우린 50까지만 하기로 하자. 여긴 중요한 이유가 있단다. 뭐냐구? 많이 쓰면 손 아프잖아. 

자, 우선 1은 합성수도, 소수도 아닌 거 알지? 1부터 확 그어버려.

2는 어떠니? 소수지? 2는 소수니까 동그라미를 해줘.

그럼 4는 어때? 1과 4이외에 2도 약수로 가지고 있으니까 약수가 3개 이상이 되어 4는 합성수야. 다시 말해서, 2배수부터는 1배수를 약수로 가지게 되니까 무조건 합성수가 되는 거야. 소수가 아니니까 그어야겠지?

2의 2배수부터 찾아볼까? 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50.

휴우, 많기도 하네. 이건 다 합성수야. 확 그어버려.

자, 그럼 3을 살펴볼 차례구나. 3도 소수지? 일단 동그라미를 해줘.

이제 3의 2배수부터 살펴보자. 2배수부터는 무조건 합성수라는 거 알지? 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48.

이것도 많네. 역시 그어버리자.

4는 이미 합성수라고 그어져 있고, 5를 할 차례네. 5는 소수니까 동그라미를 하고, 5의 배수를 살펴보자.

10, 15, 20, 25, 30, 35, 40, 45, 50. 이건 5의 2배수로 합성수니까 그어버리도록 해.

6은 이미 합성수라고 그어져 있으니 이제 7을 해보자. 7은 소수니까 동그라미를 하고, 7의 배수를 살펴보자.

14, 21, 28, 35, 42, 49. 이것 역시 7의 2배수로 합성수이니 그어버려.

이제 비어있는 곳에 모두 동그라미를 하면 50까지의 소수를 모두 찾은 거야.

왜 7까지만 하냐고? 꼭 알 필요는 없지만 일단 알려줄게. 그냥 참고로 알고 있어. 똑같은 수를 곱했을 때, 구하려고 하는 수를 넘지 않으면 돼. 이게 무슨 말인지 모르겠지?

자, 우리는 50까지 소수를 구하려고 해. 8끼리 곱해봐. 64가 되지? 50이 넘네. 그러니까 8은 쓸 수 없어. 7끼리 곱하면 49가 되지? 이건 50을 넘지 않네. 그러니까 50까지의 소수를 알아볼 때는 7까지의 소수의 2배수만 지워버리면 소수만 남게 되는 거지.

100까지의 소수를 구하려면 어떻게 해야 할까? 10끼리 곱하면 100이지? 그러니까 10까지의 수 중에 소수를 찾아서 그 배수를 지워주면 되는 거야.

10까지의 소수는 2, 3, 5, 7. 이렇게 4개구나. 50이랑 다를 것도 없네. 1부터 지우고, 2, 3, 5, 7의 2배수만 지우면 나머지는 소수야.

여기서 문제!

20까지의 소수를 구하려면 어떻게 해야 할까? 4끼리 곱하면 16이고, 5끼리 곱하면 25니까 4까지만 알아봐야겠지.

4까지의 소수는 2와 3이구나. 그러면 1부터 지우고, 2와 3의 2배수만 지우면 나머지는 소수야.

어렵다구? 어려우면 이건 굳이 알 필요 없어. 중학교에서 에라토스테네스의 체로 100이상의 수를 하는 경우는 없으니까 그냥 1을 지우고, 2, 3, 5, 7의 2배수만 지우면 돼.

 

궁금한 게 있으면 댓글 남기는 거 알지?