에라토스테네스의 체 알고리즘

에라토스테네스의 체

소수란?

1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수이다.

그럼 소수를 어떻게 구현할 것인가?

가장 보편적인 방법으로는 1~n만큼 일일이 확인을 해보는 것이다.
1부터 100 사이의 소수를 구하는 파이썬 코드이다.

n=100

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

for i in range(n+1):
  if(isPrime(i)):
    print(i)

위에 코드는 특정 숫자가 소수인지 판별하기에는 좋은 코드일 수 있다. 하지만 범위내에서 소수를 판별하기에는 시간적으로 좋지 않다.
이것을 해결하기 위해 나온 알고리즘이 에라토스테네스의 체 알고리즘이다.

에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법이다.
1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복)

이것을 파이썬 코드로 나타내면 다음과 같다.

n=1000
a = [False,False] + [True]*(n-1) ## 0, 1은 소수가 아님, 2부터 
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i): ## i배수 False로
        a[j] = False
print(primes)