[99일차] 소수 구하기 - 백준 - 1929(python - 정수론, 소수 판정, 에라토스테네스의 체)

문제 설명

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

예제 입력, 예제 출력

3 16	3 5 7 11 13

 

코드 및 설명

import math

m, n = map(int, input().split(" "))
answer = []

def gcd(i):
  if i == 1:
    return False
  
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      return False
  
  return True

for i in range(m, n+1):
  check_gcd = gcd(i)
  if check_gcd:
    answer.append(i)
  
for val in answer:
  print(val)

import math

m, n = map(int, input().split(" "))
arr = [ True ] * int(n+1)

for i in range(2, int(math.sqrt(n))+1):
  if arr[i] == True:
    j = 2
    while i * j <= n:
      arr[i*j] = False
      j += 1

for i in range(m, n+1):
  if arr[i]:
    if i != 1:
      print(i)

 

이 문제는 소수 구하기 문제로 소수 판정으로 푼 것과 에라토스테네스의 체로 푼 것 2개의 코드를 준비했다.

 

소수판정은 소수찾기에서 설명했듯이 제곱근까지 돌려주면 중복된 행위를 줄여줄 수 있기 때문에 시간복잡도에서 이득을 

 

취할 수 있는 방법이다.

 

에라토스테네스의 체는 범위가 지정되어있을 때 사용하기 편한 것 같다. 예를 들어 1000번째까지의 약수의 개수를 

 

구하라 처럼, 밑에 이미지를 보면 정말 쉽게 이해가 된다.

 

(출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

 

m부터 n의 값 사이에 약수를 출력하는 문제이기 때문에

 

arr = [ True ] * int(n+1) ---> 범위를 지정해준다. 일단 소수가 True라고 설정해주고, n+1만큼만 배열을 만들어준다.

 

1은 소수가 아니기 때문에 2부터 돌리는 데, 2를 제외한 나머지 2의 배수를 n의 값까지 False 변경해준다.  그 다음은

 

3을 제외한 나머지 3의 배수를 False 지정, 여기서 arr[i] == True이기때문에 이미 False바뀐 건 건너뛴다.

 

반복하면 

 

[True, True, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False]

 

arr가 이런 형태로 되었을 것이다.

 

m, n 까지의 범위내에 True이고, i 값이 1이 아닌 것들에 대해서 i 값을 프린트해주면 정답이 나오게 된다.

 

 

 

이미지 위에껀 에라토스테네스의 체를 이용했고, 메모리를 좀 더 사용하는 대신 속도가 빠르다.

아래는 소수 판정을 이용했고, 통과 됐으나 시간이 좀 오래 걸린다.