[백준/BOJ] 백준 코딩 알고리즘 1929번 소수 구하기 Python

문제

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

 

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

 

첫 번째 아이디어

소수 여부를 판별하는 것은 많은 알고리즘 문제에서 등장하고는 하는데,
그럴 때 보통 직관적으로 떠오르는 코드는 다음과 같다

def is_prime(n):
  if n in [0, 1]:
    return False
  else:
    for i in range(2, n):
      if n % i == 0:
        return False
    return True

print(is_prime(int(input())))

 소수라함은 1과 자기 자신 외의 수로는 나눠지면 안되기 때문에
입력받은 수에 대해서 2부터 자기 자신 직전까기 반복문을 돌면서
딱 맞아 떨어지는 (즉, 나눴을 때 나머지가 0인) 경우가 있는지 판단함으로써
소수 여부를 판별할 수 있다

 

두 번째 아이디어 (배수 개념 활용)

첫 번째 아이디어는 배수라는 개념으로 인해 반복문을 좀더 덜 돌 수 있는데 
그 코드는 아래와 같다

def is_prime(n):
  if n in [0, 1]:
    return False
  else:
    for i in range(2, n // 2):
      if n % i == 0:
        return False
    return True

print(is_prime(int(input())))

 애초에 배수는 말 그대로 특정 수가 몇 번 곱해진 것으로, 두 수의 곱으로 이루어지는 것이다
즉, 이로 인해서 2부터 (특정 수-1) 까지 나눠지는 지 판별하는 것이 아닌
2부터 (특정수//2)까지 나눠지는지 판별해도 어차피 배수 곱셈의 개념으로 인해 경우의 수를 모두 확인할 수 있다는 것이다.

이 방법을 사용한다면 첫 번째 아이디어에 비해 반복문을 절반만 돌 수 있다.

 

최종 아이디어 (에라토스테네스의 체)

하지만 많은 수에 대하여 소수 판별을 한다고 했을 때,
두 번째 아이디어를 사용한다고 해도 일일이 모두 for문을 돌고 있다면 시간이 매우 많이 소요될 것이다
이럴 때 사용하는 이론 및 개념이 '에라토스테네스의 체'라고 한다

에라토스테네스의 체의 원리는 다음과 같다

1. 가능한 모든 수를 배열로 나열한다.
2. 배열 내에서 가장 작은 수를 찾는다 

3. 가장 작은 수의 배수를 배열에서 모두 삭제한다

4. 다음으로 작은 수를 찾아 위의 과정을 반복한다

5. 더 이상 작업이 불가능할 때 까지 이를 반복한다

 

이를 코드로 구현하면 아래와 같다

MAX = 1000000
M, N = map(int, input().split())
is_prime_list = [True] * (MAX + 1)

# 작은 수부터 해당 수의 배수들을 False 처리
is_prime_list[0] = False
is_prime_list[1] = False
for i in range(2, (MAX + 1) // 2):
  j = 2
  while i * j <= MAX:
    is_prime_list[i*j] = False
    j += 1

# 남아있는 수(소수)만 출력
for i in range(M, N + 1):
  if is_prime_list[i]:
    print(i)

 

참고: https://seongonion.tistory.com/43