[알고리즘] 에라토스테네스의 체 (소수#2)

 

에라토스테네스의 체

2011. 09. 25

저번 소수#1 시간에는
주어진 소수가 소수인지 여부를 판별하는 거에 대해서알아봤습니다.
이번 시간은 에라토스테네스의 체에 대해서 알아볼려고 합니다.
에라토스테네스의 체는 소수를 구할 때 유용하게 사용되는 방법이라 할수가 있겠습니다.



먼저 에라토스테네스의 체란 무엇일가요 ?

에라토스테네스의 체는 사람의 이름입니다
그리스의 수학자이자 지리학자인 에라토스테네스는 소수를 찾는 방법을 고안하였습니다.
방법은 체란 말이 들어 가있드시 걸러낸다는 방법입니다.




그럼 어떻게 걸러내서 소수를 구하죠 ?

예를 들어 1~ 100까지 안의 솟수를 구한다면
방법은 2의 배수, 3의배수, 5의 배수를 걸러 내면
남는 수가 소수가 된다는 것입니다.




역시 말은 어렵네요 예를들어 보여주세요 !

다음과 같이 1~ 100까지 수가 있습니다.
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 ....... 100
(상당히 다 쓰기 부담스러워서 30까지만 걸러내어 볼게요 ^^;;)

먼저 2의 배수를 걸러 냅니다.
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 ....... 100

다음 3의 배수를 걸러 냅니다.
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 ....... 100

마지막으로 5의 배수를 걸러 냅니다.
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 ....... 100

그러면 남은 수를 보면
1, 7, 11, 13, 17, 19, 23, 29 ..... 남게 됩니다.
여기서 1은 소수가 아니니 제외하면
남은 수들은 소수입니다.



그럼 직접 실습을 해봅시다 !

직접 소스코드를 짜보세요

그렇다면 정말 결과는 어떨가요 ?

결과

직접 구현을 해보세요 !

                                  도움이 되셨나요 ?

                  도움이 되셨다면 리플하나 달아주는 센스 ^^