'[Public] 컴퓨터공학/알고리즘'에 해당되는 글 13건

  1. 2011.09.25 [알고리즘] 에라토스테네스의 체 (소수#2) (6)
2011.09.25 14:41
 

에라토스테네스의 체


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은 소수가 아니니 제외하면
남은 수들은 소수입니다.



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

직접 소스코드를 짜보세요





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

결과

직접 구현을 해보세요 !



                                  도움이 되셨나요 ?

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

 

Posted by 차출발 차출발

댓글을 달아 주세요

  1. 선린 2011.12.02 00:05  댓글주소  수정/삭제  댓글쓰기

    감사합니다.
    근데 2의배수 3의배수 5의배수 걸러낼때, 2,3,5는 걸러내면 안되는거 아닌가요?
    2,3,5는 소수잖아요

  2. BlogIcon 춘자 2011.12.06 22:13 신고  댓글주소  수정/삭제  댓글쓰기

    우리 형님이 제 블로그를 와 주시다니 영광입니다. ㅋㅋㅋ

  3. 지나가던 사람 2011.12.09 20:47  댓글주소  수정/삭제  댓글쓰기

    틀리신게 있으셔서 감히 말해봅니다.
    결론만 우선 말하자면 에라토스테네스의 체는 나열된 자연수의 집합에 2,3,5의 배수가 아닌 k를 제외한 모든 k의 배수를 지우는 것으로 구하실 수 있습니다.
    일단 소수는 1과 자기자신으로만 나눌 수 있는 수라는 것을 아실 겁니다. 하지만 2, 3, 5의 배수만을 제외한다면 더 큰수로 나누어 떨어지는 수들은 걸러지지 않게됩니다.
    실제로 저 예제에서 49, 77, 91은 모두 7로 나누어 떨어지기 때문에 소수가 아닙니다.

  4. 지나가다 2013.12.15 02:32  댓글주소  수정/삭제  댓글쓰기

    11^2 > 100 이므로 1~100까지의 소수는 최소 11보다 작은 소수인 7의 배수까지도 걸러내야 됩니다.
    7의 배수도 지워야 위에 분이 언급하신 소수가 아닌 49, 77, 91도 걸러내집니다.