에라토스테네스의 체(소수 찾기)

소수인지 확인하는 함수

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

• 위의 코드는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법으로, 소수의 정의에 충실한 방법이면서 무식하지만 가장 강력한 방법이다.
• 한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.
• 소수를 구하기 위해 에라토스테네스가 제안한 방법은 다음과 같다.

---

에라토스테네스의 체

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

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 수(2)를 소수로 채택하고, 나머지 제일 작은 수(2)의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 수(3)을 소수로 채택하고, 나머지 제일 작은 수(3)의 배수를 모두 지운다.
4. 4는 2의 과정에서 지워졌으므로 pass
5. 지워지지 않은 수 중 제일 작은 수(5)를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
6. (반복)

---

에라토스테네스의 체 파이썬으로 구현

def sieve_of_Eratosthenes(num):
  a = [False, False] + [True]*(num-1)
  primes=[]

  for i in range(2,num+1):
    if a[i]:
      primes.append(i)
      for j in range(2*i, num+1, i):
          a[j] = False

  return primes

print(sieve_of_Eratosthenes(100))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]