[Lv.?_Map] 에라토스테네스의 체_(소수 찾는 공식)

우선 소수 찾는 알고리즘 테스트를 앞서 소수에 관해서 더 공부를 해야한다고 느낀뒤 공부를 시작했다!!

우선 소수의 정의는 1과 자기 자신으로만 나누어 떨어지는 1보다 큰 양의 정수이다!
즉 1과 자기자신만을 약수로 갖는 숫자인 것이다!

소수를 찾는데에는 제곱근을 이용해서 소수를 찾는 방법, 순서대로 나누어서 찾는방법 등 여러가지 방법이 있지만!

지금 내가 알아보고자 하는것은 고대 그리수 수학자인 에라토스테네스가 발견한 방법이다!!
에라토스테네스의 체 라는 방법인데 자연수를 체로 쳐서 소수를 골라낸다는 뜻에서 이름이 붙여졌다고 한다.

우선 1부터 자연수를 순서대로 적는다!

두번째로 2만 남기고 2의 배수를 모두 지운다!!

세번째로는 3만 남기고 3의 배수를 모두 지운다!

같은 방법으로 5만 남기고 5의 배수를, 7 등등 차근차근 지우다 보면 소수만 남게 되는데!!
이와같이 체에 걸러서 남은 숫자가 바로 소수이다!
이것이 바로 에라토스테네스의 체 라는 방법이다!

이렇게 남았는데 소수의 갯수는 무한함으로.... 앞으로 알고리즘 문제를 풀 때 잘 참고해서 풀어보자!!

이미지 출처와 내가 공부한 블로그는
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=falcon2026&logNo=221240012317
이 블로그에서 찾아서 공부하고 이미지를 가져왔다!