에라토스 테네스의 체란?여러 개의 수가 소수인지 아닌지 판별할 때 사용하는 대표적인 알고리즘이다.소수를 구하는 가장 기본적이고 이해하기 쉬운 방법 중 하나이다. 어떻게 동작하는가?리스트 생성: 2부터 원하는 최대 숫자 N까지의 리스트를 만듦첫 번째 소수 선택: 가장 작은 소수인 2부터 시작배수 제거: 선택한 소수의 배수를 리스트에서 제거하거나 표시다음 소수 찾기: 리스트에서 다음으로 남아있는 수를 선택하고, 이 수의 배수를 제거반복: 이 과정을 N의 제곱근까지 반복 시간 복잡도는??에라토스테네스의 체의 시간 복잡도는 놀랍게도 O(N log log N)이다.log log N은 매우 천천히 증가하는 함수로, N이 실용적인 범위 내에서는 거의 상수에 가깝다.즉, 해당 알고리즘은 사실상 선형 시간에 가까운 ..
