[알고리즘] 에라토스테네스의 체

에라토스테네스의 체

 소수를 빠르게 구하기 위한 방법 중 하나로 에라토스테네스가 발견하였다.

소수를 구하는 가장 기본적인 방법은 모든 수를 돌아보며 1과 자기 자신 이외에 나눠지는 수가 있는지 확인하는 것이지만 모든 수를 확인해야되기 때문에 시간 복잡도가 커지게 된다.

 

이때 에라토스테네스의 체를 사용할 수 있는데, 에라토스테네스의 체는 2부터 3 , 4 , 5, ... 이렇게 숫자를 증가시키면서 본인의 배수를 지워간다. 이렇게 체로 걸러내듯이 숫자들을 지워가면 이미 지워진 수들은 확인할 필요가 없기 때문에 숫자가 커질수록 확인해야되는 숫자들도 줄게 되고 소수를 훨씬 더 적은 수만 확인하고도 찾아낼 수 있다.

 

 추가적으로 N까지의 소수를 찾을 때는 N의 제곱근까지만 찾으면 된다.  아래 그림의 예를 들자면 120의 경우 10의 배수들까지만 지워주면 되는데 11의 경우 11 * 2, 11 * 3, 11 * 4, ... , 11 * 10 을 지워야 하지만 11에 곱해지는 숫자들이 1~10이 이미 이전에 2, 3, 4의 배수들을 확인하면서 이미 지워졌기 때문이다. 11 * 11은 121이기 때문에 포함이 안된다. 그래서 제곱근 보다 작은 정수까지만 확인을 하면 이후의 숫자들은 확인할 필요가 없다.

 

출처 - https://velog.io/@htchoi1006/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

 

파이썬 코드 구현