에레스토테네스의 체

안녕하세요. 옆집컴공생입니다. 오늘은 범위 내에 소수를 전부 구해주는 에레스토테네스의 체를 배워 보겠습니다. 

 

소수란 영어론 Prime Number(프라임 넘버) 라고 하는 '약수가 1과 자기자신 뿐인 수'를 의미합니다. 예로 들면 2,3,5,7 등이 있겠습니다. 간단한게 소수를 구하는 반복문을 볼까요?

 

다음 함수는 x가 소수이면 true , 합성수(소수가 아닌 수)이면 false를 반환해주는데요. 1과 x를 제외한 나머지 모든 수를 for 문으로 돌면서 나누어지는 체크해보는겁니다. 사실 이 방법은 굉장히 오래 걸리는 편인데요. 

 

사실 소수를 판별하는데는 소수의 제곱근 까지만 체크를 해주면 됩니다. 왜일까요? 

 

합성수를 20을 생각해봅시다. 20의 약수는 2, 4, 5 ,10 입니다.( 1과 자신은 제외했습니다.) 

이 수들을 보면 매칭 되는 수의 쌍이 보입니다. 2 x 10, 4 x 5 입니다. 즉 2만 계산하면 되고 4만 계산하면 되는겁니다. 만약 2가 계산되면 10이 되는 것과 동일하기 때문입니다. 똑같은 형식임으로 계산 수가 절반이 줄어든거죠! 20의 제곱은 다음과 같습니다. 

20의 제곱근

그러니 4까지 해주면 되는거겠죠?

 

이렇게 소수 체크를 수의 제곱근까지만 계산하면 된다는 걸 알 수 있습니다.

제곱근까지만 약수 체크

 

그외에도 약수를 체크하는데는 여러가지 방법이 있습니다. 다음 링크를 보시면 좀 더 많은 방법을 볼 수 있습니다. https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

소수판별법 - 위키백과, 우리 모두의 백과사전

 

 

 

---

에레스토테네스의 체

 

에레스토테네스의 체는 범위까지에 모든 소수를 나타내주는 건데요. 방식은 굉장히 간단합니다!

 

1. 2부터 자기자신을 제외한 자신의 배수를 없애준다.

2. 없어진 수는 넘어간다. 

 

이것만 반복을 해주면 굉장히 빠른 방식으로 소수를 다 구할 수 있습니다. 

 

그럼 간단하게 20까지만 해볼까요?

 

 

1) 2의 배수를 없애준다.

2) 3의 배수를 없애준다.

3) 4는 이미 없어졌기 때문에 5로 넘어갑니다. 5의 배수가 없으니 7로 넘어갑니다. 7의 배수가 없습니다........

 

이처럼 2, 3, 5, 7, 11, 13, 17, 19 가 소수인 걸 알 수 있습니다. 

굉장히 빠른 느낌이죠? 그럼 코드를 한번 볼까요?

십만 까지의 소수를 굉장히 빠르게 구해봤습니다. 

 

 

 

오늘은 에레스토테네스의 체를 배워보았습니다.ㅎㅎ 소수를 판별하는데 대회등에서도 종종 출제되는 문제라 익혀두는게 좋을거 같습니다. 수고 많으셨습니다.