에라토스테네스 썸네일형 리스트형 Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기 이전 1 다음