[자료구조 및 알고리즘] 에라토스테네스의 체

소수의 정의

 

1을 제외한 자연수 중, 1과 자기 자신만을 약수로 가지는 수를 의미한다.

 

소수 판별

def prime_num(x):
  for i in range(2,x):
    if not x % i: return "합성수"
  return "소수"

효율성 개선

def primenum(x):
  for i in range(2, int((x**0.5)+1)): # x의 제곱근까지만 나누어떨어지는지 확인
    if not x % i: 
      return "합성수"
  return "소수"

x의 제곱근까지만 나누어떨어졌는지 확인하는 이유는, x의 약수를 펼쳐보면 x의 제곱근 값을 기준으로 대칭을 이루고 있기 때문이다. 이를테면 9는 1, 3, 9를 약수로 가지고 있고, 20은 1, 2, 4, 5, 10, 20을 약수로 가진다. 딱 나누어 떨어지지 않는 경우에는 제곱근 값에서 버림을 해주면 된다. 예를 들어 20의 경우 4.xx를 제곱근 값으로 가지지만 4까지만 확인하면 된다.

 

에라토스테네스의 체

# 1000까지의 숫자 테이블을 만들고 소수 판별
num = 1000
numtable = [True]*1001
def primenum(n, table):
  for i in range(2, int((n**0.5)+1):
    if table[i]:
      j = 2
      while i*j <= n:
        table[i*j] = False
        j += 1
      # 아래부터는 출력단계
      for i in range(2, n+1):
        if table[i]: print(i, end=' ')
        
primenum(num, numtable)

에라토스테네스의 체는 범위 안에 있는 소수들을 출력하는 알고리즘이다. 순서는 다음과 같다.

 

1. 2부터 n까지 모든 자연수를 나열한다.

2. 남은 수 중에서 처리하지 않은 가장 작은 수를 선택한다.

3. 남은 수 중에서 i의 배수를 모두 제거한다. 이때 i는 제거하지 않는다.

4. 더 이상 반복할 수 없을 때까지 위 과정을 반복한다.

 

위 알고리즘은 매우 빠르게 동작하기는 하지만, 데이터 범위가 커지면 메모리 문제가 발생할 수 있다. 리스트에 큰 값을 할당하기 때문인데 큰 값을 쓸 때는 다른 방법을 이용할 거 같기는 하다.