백준 : 소수 구하기 - 1929

예제 입력 1 

3 16

예제 출력 1 

3
5
7
11
13

 

이 문제는 실버 치고도 정말 쉬운 문제이다. 아마 소수 관련 문제 중에 풀어본 사람이라면 제곱근을 생각할 수 있을 것 같다.

 

N, M = map(int, input().split())

for i in range(N, M+1):
    if i == 1: 
        continue
        
    for j in range(2, int(i**0.5) + 1): # 기존 제곱근 생각해서
        if i % j == 0: 
            break
    else: 
        print(i)

 

그런데 여기서 이때 소수 관련 문제를 풀면서도 에라토스테네스의 체라는 말을 한번쯤은 다른 풀이를 보다가 알 수 있을 것 같은데 생각난 김에 복습할 겸 다시 글을 적고자 한다.

[Algorithms/Python] 에라토스테네스의 체

에라토스테네스의 체는 특정 범위 내의 모든 소수를 빠르고 효율적으로 찾아내는 알고리즘이다.

 

고대 그리스의 수학자 에라토스테네스가 발견했으며, 그 원리는 다음과 같습니다.

핵심 아이디어: "소수가 아닌 수(합성수)는 그 수보다 작은 소수의 배수이다." 라는 원리를 이용한다.

즉, 범위 내의 모든 수를 펼쳐놓고, 소수의 배수들을 차례대로 지워나가면 결국 소수만 남게 된다는 말이다.

작동 방식:

1. 배열 생성: 2부터 N까지의 숫자를 모두 포함하는 배열을 만든다. 처음에는 모두 '소수'라고 가정한다.
2. 소수 판별 시작: 가장 작은 소수인 2부터 시작한다.
3. 배수 지우기: 2를 소수로 확정하고, 2의 배수들(4, 6, 8, ...)을 모두 배열에서 '소수가 아님'으로 표시한다.
4. 다음 소수 찾기: 다음으로 지워지지 않은 숫자(3)를 찾는다. 3은 소수이다.
5. 배수 지우기 반복: 3의 배수들(6, 9, 12, ...)을 모두 '소수가 아님'으로 표시한다. (이미 지워진 수는 그냥 둡니다.)
6. 과정 반복: 이 과정을 계속 반복한다. 다음 소수인 5를 찾아 그 배수들을 지우고, 다음 소수인 7을 찾아 그 배수들을 지운다.
7. 종료 조건: 이 과정은 N의 제곱근까지만 반복하면 된다. 왜냐하면 N보다 작은 합성수 n은 반드시 √N 보다 작거나 같은 소인수를 가지기 때문이다.
8. 결과: 이 과정이 끝나면 배열에 '소수'로 남아있는 숫자들만 골라내면 된다.

https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

기본 코드는 다음과 같은 형태이다. 이를 바탕으로 문제를 해결하고자 하면

import sys
import math

# sys.stdin.readline()을 사용하면 더 빠르게 입력받을 수 있습니다.
m, n = map(int, sys.stdin.readline().split())

를 소수(True)로 가정합니다.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

# 에라토스테네스의 체 알고리즘을 수행한다.
# 2부터 N의 제곱근까지만 확인하면 된다
for i in range(2, int(math.sqrt(n)) + 1):
    # i가 소수인 경우
    if is_prime[i]:
        # i를 제외한 i의 모든 배수를 소수가 아니라고 표시한다.
        # j를 2부터 시작하여 i*j가 n을 넘지 않을 때까지 반복한다.
        j = 2
        while i * j <= n:
            is_prime[i * j] = False
            j += 1

# M부터 N까지의 범위에서 소수인 숫자만 출력한다.
for i in range(m, n + 1):
    if is_prime[i]:
        print(i)