[python/알고리즘] 에라토스테네스의 체 | 소수 찾기

에라토스테네스의 체

• 합성수를 지우는 방식으로 소수를 찾는 방법.

  1. 1은 제거
  2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
  5. (반복)

코드

n = 1000
a = [False, False] + [True] * (n-1) # 소수 여부를 저장할 리스트
primes = [] # 소수를 저장할 리스트

for i in range(2, n+1):
  if a[i]: # 만약 소수라면
    primes.append(i) # 소수 리스트에 넣고
    for j in range(2*i, n+1, i): # i의 배수들은 소수가 아님을 표시 
        a[j] = False
print(primes)

참고자료 | wikidocs 2. 소수 구하기 - 에라토스테네스의 체