에라토스테네스의 체

알고리즘 문제에 자주 등장하는 소수를 빠르게 구하는 방법.

1부터 n까지 숫자가 들어있는 배열을 처음부터 순회하면서, 선택된 수의 배수들을 배열에서 제거하는 방식으로 구현한다.

일반적으로 소수를 구한다면, n까지 2부터 반복문을 돌며 일일이 나머지 연산을 시도하기때문에 O(N) 만큼 걸린다.

에라토스테네스의 체는 이중반복문을 돌지만,O(Nlog(logN)) 의 빠른 속도를 자랑한다.

(Gif 출처: 위키피디아)

기타

• 끝자리가 0인 값에 소수점이하 n자리 이상 출력하고 싶다면, round() 대신 서식문자나 format(), f-string 을 사용해야한다.

num = 40
print(f'소수점이하 3자리: {num:.3f}')
# 40.000