백준 1929 소수 구하기

 

문제

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

입력

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

출력

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

예제 입력 1 

3 16

예제 출력 1

3
5
7
11
13

 

문제 접근

소수와 관련된 문제들이 그렇듯 이 문제 또한 에라스토스테니스의 체를 사용하는 것이 시간 복잡도에 있어서 가장 효과적이다. 첫 풀이는 N+1 크기의 numbers라는 리스트를 통해 1부터 N까지의 수를 리스트의 index를 통해 확인하고 소수가 아니면 1로 표시하는 방법을 택했다. 그림으로 표현하면 다음과 같이 되는데 

이를 통해서 알고리즘 코드를 작성하면 다음과 같이 된다

문제 풀이

M,N = map(int, input().split())
numbers = [0]* (N+1)
for i in range(2,N+1):
  j = 2 #에라스토스테니스의 체에 활용할 변수
  while i*j <= N: #주어진 볌위까지만 조사
    if numbers[i*j] == 0: #이 경우는 소수이다
      numbers[i*j] = 1 #해당 소수를 기준으로 배수를 1로 채운다
    j += 1
for i in range(M,N+1):
  if numbers[i] == 0 and i != 1: #1은 소수가 아니므로 제외 대상이다
    print(i)

 

이 풀이도 성공은 하지만 전에 에라스토스테니스의 체를 활용한 코드를 찾아본 결과 다음과 같은 풀이도 존재했다.

 

또 다른 풀이

m,n = map(int,input().split())

for i in range(m,n+1):
  if i == 1:
    continue
  for j in range(2,int(i**0.5)+1):
    if i%j == 0:
      break
  else:
    print(i)

처음에 혼자 생각한 풀이가 더 직관적이지만 위 풀이의 경우 시간복잡도와 메모리 면에서는 더 효율적이다. 왜냐하면 numbers라는 리스트를 사용하지 않고 소수를 발견한 즉시 print하여 시간 복잡도 면에서도 더 우수하다. 특히나 저 두 번째 for문의 조건을 보면 int(i**0.5)+1즉 조사할 수 i를 root한 연산의 의미를 생각해보면 다음 그림으로 표현이 가능하다.

해당 알고리즘은 시간복잡도가 O(N**1/2)로 확연하게 줄어든다. 구현 면에서 해당 알고리즘에 익숙해지도록 하자. 문법 자체는 솔직히 직관적이지 않지만 학습할 가치가 있다.