소수(prime number)는 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 에라토스테네스의 체 원리구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.배열의 끝까지 위의 방법을 반복한 후 배열에서 남아있는 모든 수를 출력한다.이중 for문을 이용하므로 O(N2) 정도라고 판단할 수 있다.하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만일반적으로 O(Nlog(logN))이다.그 이유는 배수를 삭제하는 연산으로실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다. N의 제곱근까지 탐색하는 이유어떤 수가 소수인지 판단할 때 그 수의 제곱근 ..
