에라토스테네스의 체(2022.04.13)

목차

에라토스테네스의 체

소수판정의 가장 기본이 되는 에라토스테네스의 체이다.

소수는 약수가 1과 자기자신만을 가지는 수이다. 소수를 구하는 알고리즘을 찾아보자.

알기 쉽게 예를 들어보겠다.

1~50까지의 소수

1부터 50까지의 수 중 소수를 찾는 방법을 보자

먼저 숫자를 다 적어본다.
그리고, 제일 첫번째 소수인 2의 배수를 다 지워준다.

지워주는 이유를 생각을 해보면, 소수는 1과 자기자신만을 약수로 가지는 수 이다.
어떤 수의 배수는 소수가 될 수 없다.

그러므로 범위내의 소수의 배수를 다 지워주면, 소수만 남게된다.

그렇게 2의 배수를 지우고,

3의 배수

5의 배수

7의 배수

이렇게 까지만 지워주면 나머지 수

들은 전부 소수가 된다.

왜 7까지만 지워줄까?

근데 앞에서 그러므로 범위내의 소수의 배수를 다 지워주면, 소수만 남게된다.라고 설명했었는데,
왜 7의 배수까지만 지워주는 걸까?

그 이유는 어떤 수 m 이 n보다 작은 합성수 라면, m = ab이다.

이때 a, b중 하나는 n^0.5이하의 자연수이다.
따라서, n^0.5의 배수들만 지워주면 자연스럽게 모든 합성수를 제외할 수 있다.

구현해보자

이를 위해 적당한 문제
백준 1929번, 이동 문제를 풀어보자

입력값 N에 대하여, 시간복잡도는 O(Nlog(logN))으로, 거의 선형시간에 가깝다

소수를 구하는 문제는 정말 많기도하고, 또 소수를 구하는 방법도 여러가지다.
소수를 구하는 방법을 보면서 공부를 하다보면, 정말 신비한 수라고 느꺼지기도 한다.

그 소수를 구하는 가장 기본적인 방법인 에라토스테네스의 체를 알아봤다.