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

소수 구하기

소수란?

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

소수 구하는 코드 구현

다음 코드는 우리가 흔히 알고 있는 소수를 찾는 코드이다.

# 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)

위 코드는 전혀 문제없는 코드이지만 n 의 단위가 커질수록 시간이 오래걸린다. 이처럼 시간이 오래걸리는 문제를 해결할 수 있는 방법을 알아보자.

---

에라토스테네스의 체

에라토스테네스의 체 란?

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다.

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 ‘에라토스테네스의 체’ 라고 부른다.

에라토스테네스의 체 코드 구현

1. 1~n 까지 숫자 나열
2. 1은 소수가 아니니 삭제
3. 2의 배수를 모두 삭제
4. 3의 배수를 모두 삭제
5. 4의 배수를 모두 삭제 해야 하지만 2의 배수이므로 넘어감
6. 5의 배수를 모두 삭제
7. …

def sieve(n):
    prime = [True] * (n + 1)     # 0 ~ n까지 True로 초기화
    prime[0] = prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(n**0.5) + 1):
        if prime[i]:             # i가 소수일 때만
            for j in range(i * i, n + 1, i):
                prime[j] = False # i의 배수를 제거

    return prime                 # 소수 여부 목록 반환

n = int(input("n을 입력하세요: "))

prime = sieve(n)

for i in range(1, n + 1):
    if prime[i]:
        print(i, end=" ")