[python] 파이썬을 이용해 소수 추출하기 / 에라토스테네스의 체 방법으로 추출하기

문제(1) 설명

2와 입력된 자연수 n 사이의 모든 소수를 출력해보자.

코드

def check_prime(n) :
  i = 2
  while i < n :
    if n%i==0:
      break
    i += 1 
  if i == n :
    print(f'{n}은 소수')
  else :
    print(f'{n}은 합성수')

n = int(input("자연수 하나를 입력하시오 :"))
i = 2
while i <= n :
  check_prime(i)
  i += 1

문제(2) 설명

에라토스테네스의 체 방법으로 소수를 구해보자. 
1단계 : 가장 작은 소수인 2부터 n까지의 숫자들 중에서 2의 배수인 숫자들은 제거한다.
2단계 : 남아 있는 숫자들 중에서 그 다음으로 작은 소수인 3,5,7... 등을 1단계를 반복한다.
3단계 : 지워지지 않은 모든 수는 소수이다.

코드

def calc_prime(n):
  check = [1 for i in range(n+1)]
  i = 2
  k = 1
  while i < n+1:
    if check[i] == 1:
      print(i)
      while i*k < n+1 :
        check[i*k] = 0
        k += 1
      k = 1
    i += 1

n = int(input("자연수를 입력하시오 :"))
calc_prime(n)

 

해설

check = [1 for i in range(n+1)] 을 통해 배열의 크기를 초기화 해준다. 2는 가장 작은 소수이므로 첫 번째로 확인을 한다. check[i] == 1 이면 소수이며 check[i*k]=0을 통해 소수의 배수들은 모두 0을 넣어 걸러낸다.
이를 반복하다 보면 소수만 남게된다.