에라토스테네스의 체 for 코딩테스트

 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

 

코딩테스트에서 가끔 나오는 소수찾는 알고리즘이다.

 

처음 문제를 접했을때 어떤 방식으로 찾아야 하는지에 대한 깊은 고민을 해봤지만,

 

역시나, 이렇게 복잡한 고민은 고대 그리스 수학자들이 이미 해결해 두었다.

 

 

찾는 방법은 아래와 같다.

 

1) 2는 소수이다. 2의 배수를 모두 지운다.

2) 3은 소수이다. 3의 배수를 모두 지운다.

2) 5는 소수이다. 5의 배수를 모두 지운다.

...

반복

위 알고리즘을 요약하는 좋은 예시

 

이를 코딩으로 구현해보자.

 

# 특정 정수 범위 이내의 소수를 찾는 방법

n = int(input())  #정수 입력

a = [False,False] + [True]*(n-1)  # 앞의 1, 2는 False(=0), 나머지 수는 모두 True(=1)인 리스트 생성
primes = []  #소수를 담을 빈 리스트 생성

for i in range(2,n+1): 
    if a[i]:    #현재 값이 true라면 소수 리스트에 넣기
        primes.append(i)
        for j in range(2*i, n+1, i):  #넣은 후, 넣은 수의 배수를 False로 변경
            a[j] = False
print(prime)  #소수 리스트 출력