소수 구하기 : 에라토스테네스의 체 소수 : 1과 자기 자신 외에 약수가 존재하지 않는 수 에라토스테네스의 체 이중 반복문을 사용 : 시간복잡도 $ O(N^2) $ 단 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하므로 $ O(Nlog(logN)) $ 과정 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우, 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하며 지운다 특정 숫자의 배수는 소수가 아니므로 지운다 2부터 시작하는 이유 : 1은 소수가 아니므로 & 1은 모든 수의 약수이므로 처음으로 선택된 숫자는 지우지 않는다 : 배수가 아닌 처음으로 선택된 숫자는 소수이므로 리스트의 끝까지 2를 반복한 후, 리스트에서 남아있는 모든 ..
