|
에라토스테네스의 체
우리는 간단하게 에라토스테네스의 체로 1 ~ 30 사이에 있느 소수들을
찾아 보려 합니다. 1 ~ 30 을 다음과 적어 봅시다.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
이제 이 숫자들 중에서 소수가 아닌 것들을 하나씩 제외할 것입니다.
우선 1 은 소수가 아니라 했습니다. 네, 그러니까 소수 닙니다.
그러니까 1 을 제외시킵니다. 그리고
2 는 소수 입니다. 그런데 2 의 배수들은 다 소수가 아닙니다.
4, 6, 8, 10, 12, 14, 16, 18, 20, ...
그러니까 이것들을 다 제외 합시다.
그래서 다시 적어 보면 이렇습니다.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
이렇게 하니까 이미 반이 줄어 들었습니다.
이제 3 입니다. 3 은 소수 입니다.
그런데 3 의 배수들은 다 소수가 아닙니다.
9, 15, 21, 27, ...
그러므로 이들을 제외 시킵니다.
다시 적어보면 다음과 같습니다.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
그런데 이제 25 를 생각해 봅시다. 그것은 5 의 배수입니다.
남은 것들을 생각해 봅시다. 이것들은 다 소수입니다. 그렇죠?
그래서 이렇게 하여 소수들을 찾을 수 있는 것입니다.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
입니다.
자 어떻습니까? 1 ~ 30 의 소수를 찾는 방법 정말 간단하죠?
그렇습니다. 에라토스테네스의 체를 이용하면 이렇게 간단합니다.
그런데 말입니다.
여러분들이 이렇게 실제로 소수를 찾아보면 알 것입니다.
소수를 찾는 일은 실은 여간 까다롭고 어려운 일이 아닌 것입니다.
어떤 수에서 그 약수를 일일이 찾아내야 하는 것입니다.
물론 에라토스테네스의 체가 있습니다. 그러나 이것은
숫자가 작으면 비교적 쉽게 찾을 수 있으나 그러나 ...
결론은 불가합니다! 그것은 왜냐구요?
생각을 해 봅시다.
숫자가 100 ~ 1000 으로 작으면 그렇게 비교적 쉽게
찾을 수 있을 것입니다.
그러나 예를 들어 숫자가 이렇게 커진다면?
900156819023803961039
그러면 어떨까요?
그러면 이 약수들을 어떻게 찾을 수 있을까요?
여러분들은 이런 숫자들에 대하여 그 약수들을 찾을 수 있습니까?
여러분들은 결코 그렇게 할 수 없을 것입니다.
그래서 이렇게 과거에 소수를 찾아내는 일은 흥미로운 과제였나 봅니다.
잠시 여러분들의 머리를 쉬게 할 겸하여 이 소수에 얽힌 이야기를
여러분들에게 들려 주겠습니다.
|