에라토스테네스의 체는 소수를 찾는 알고리즘이다.
고대 그리스의 수학자 에라토스테네스가 발견하여 이름이 에라토스테네스의 체라고 지어졌다고 하는데
이에 대해 간단히 알아보려 한다.
일단 설명에 앞서 소수가 무엇인지부터 알아야 한다.
소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다.
예를들어 13의 경우 1과 13 외의 숫자로 나눴을 때 나머지가 0인값이 없기 때문에 소수에 속한다.
반면 15의 경우 1과 15 외에도 3, 5로 나눴을 때 나머지가 0이기 때문에 소수라고 할 수 없다.
이 점을 알고 에라토스테네스의 체에 대해 알아보도록 하자.
우선 알고리즘의 방법은 매우 간단하다. 아래의 사진을 보면 한번에 이해가 될 것이다.
소수의 조건중 1보다 큰 자연수가 있기 때문에 2부터 계산을 시작한다.
그리고 2의 배수들을 전부 지워준다. 2의 배수일 경우 2로 나눠떨어지기 때문에 전부 소수가 아니기 때문이다.
그리고 2의 배수에 속하지 않는 숫자들중 최소값에서 같은 방법으로 전개한다.
3의 배수를 전부 지워주고 그리고 2의배수, 3의배수에 속하지 않는 값중 가장 작은값부터 다시 시작한다.
이러한 방법을 범위 내에서 계속해서 반복하면 소수를 찾을 수 있다.
이 방법은 결국 숫자 n의 배수인 경우 소수가 아닌 점을 활용한 것이다.
이런 과정을 반복하면 결국 그림은 이렇게 된다.
이렇게 Prime numbers에 소수만 남아있는 것을 확인할 수 있다.
에라토스테네스의 체의 시간복잡도가 O(n log(logn))로 빠른편에 속하지만 코드가 다소 복잡할 수 있다는 단점도 있다.
이왕이면 빠른게 좋긴 하니 사용할 수 있다면 사용하는게 좋지 않을까
에라토스테네스의 체를 활용한 문제는 아래의 링크를 통해 확인할 수 있다.
[C++] 백준 4948
백준의 4948번 문제 베르트랑 공준 문제이다. https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존
loasd.tistory.com