[Coding Test] 소수 구하기

에라토스테네스의 체 원리

• 구하고자 하는 소수의 범위만큼 1차원 배열 생성
• 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 삭제, 이때 처음으로 선택된 숫자는 삭제하지 않음
• 배열의 끝까지 반복한 후 배열에 남은 수를 출력
• N의 제곱근까지만 탐색하면 
• for문을 생략하게 만들어 시간 복잡도는 O(Nlog(logN))

primes = [True] * 1000001
primes[0] = False
primes[1] = False
for i in range(2, int(math.sqrt(1000001)) + 1):
    if primes[i] == False:
        continue
    for j in range(i * 2, 1000001, i):
        primes[j] = False