백준 1929번(Python): 소수 구하기(에라토스테네스의 체)

Ohback·2025년 8월 22일

1929 1978 백준 에라토스테네스의 체 코테

Algorithm-Study

목록 보기

5/6

닮은 꼴 문제, 1929번 vs 1978번

1929번 소수 구하기는 1978번의 업그레이드 버전으로, 두 문제의 가장 큰 차이점은 문제에서 요구하는 소수의 개수와 소수의 범위이다.
1929번에 접근하기 전에 1978번을 풀고 가면 좋을 듯 싶어서 두 문제 다 가져와봤다.

1. 1978번 - 소수 찾기

1978번 문제는 주어진 N개의 수 중에서 소수의 개수를 세는 문제로 N의 최대값은 100이고, 주어지는 자연수들의 최대값은 1,000이다.

작은 범위: 각 수가 1,000 이하로 매우 작다.
필요한 연산: N개의 수를 각각 소수인지 판별하면 된다.

풀이 방법

입력 받은 값(n)들을 하나씩 for문으로 돌려서
2부터 n-1까지의 숫자로 나누었을 때 나머지가 0이면 소수가 아니라고 판별
(소수는 1과 자기 자신(n)으로만 나눠떨어지므로)
그래서 소수가 아닌 인자들을 판별해내고 나누어 떨어지지 않은 수를 is_prime == True로 판단하여 그 수를 센다.

# n값 입력 받고
# numbers 입력 받은 다음에
# 소수 몇 개인지 세야하니까 count = 0 세팅해주고
# for문으로 numbers에 있는 인자들 하나씩 불러와서
# 1보다 클 때(1은 소수가 아니니까 제외시키기)
# 우선 is_prime = True로 세팅해주고
# 다시 for문으로 2부터 num사이의 숫자와 대조하여 나눴을 때 나머지가 0이면 is_prime = False(소수는 1과 자기 자신만을 약수로 가지니까)
# 그 다음 두번째 for문 빠져 나와서 is_prime == True면 count += 1 한 뒤
# 첫번째 for문 나와서 print(count)

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

count = 0
for num in numbers:
    print(f"현재 num: {num}")
    if num > 1:
        is_prime = True
        for i in range(2, num):
            print(f" - 현재 i: {i}")
            if num % i == 0:
                is_prime = False
                print(f"{num}은(는) 소수가 아닙니다.")
                print("=============")
                break
        
        if is_prime == True:
            count += 1
            print(f"{num}은(는) 소수입니다. 현재 소수 개수: {count}")
            print("=============")

    else:
        print(f"{num}은 소수가 아닙니다.")
        print("=============")

print(f"총 소수 개수: {count}")

흐름을 눈으로 봐야 편할 것 같아서 중간 중간 print문을 넣어 실행했는데,
아래는 출력된 값들로 코드가 어떻게 작동하는지 쉽게 알 수 있도록 도와준다.

# 흐름 살펴보기
현재 num: 1
1은 소수가 아닙니다.
=============
현재 num: 3
 - 현재 i: 2
3은(는) 소수입니다. 현재 소수 개수: 1
=============
현재 num: 5
 - 현재 i: 2
 - 현재 i: 3
 - 현재 i: 4
5은(는) 소수입니다. 현재 소수 개수: 2
=============
현재 num: 6
 - 현재 i: 2
6은(는) 소수가 아닙니다.
=============
현재 num: 7
 - 현재 i: 2
 - 현재 i: 3
 - 현재 i: 4
 - 현재 i: 5
 - 현재 i: 6
7은(는) 소수입니다. 현재 소수 개수: 3
=============
총 소수 개수: 3

2. 1929번 - 소수 구하기

1929번 문제는 M이상 N이하의 모든 소수를 찾는 문제로 M과 N의 최대값은 1,000,000이다.

넓은 범위: 소수를 찾아야 하는 범위가 1,000,000까지로 매우 넓다.
필요한 연산: 이 범위 안의 모든 소수를 찾아야 한다.
풀이 방법: 1978번처럼 모든 숫자를 일일이 나눗셈으로 판별하면 시간이 너무 오래 걸린다. 이럴 때는 에라토스테네스의 체를 사용하여 N까지의 모든 소수를 미리 구해놓는 것이 훨씬 효율적이다. 에라토스테네스의 체는 $O(N \log\log N)$ 의 시간 복잡도로 소수를 찾아내기 때문에, 넓은 범위의 소수들을 한 번에 빠르게 계산하는 데 적합하다.

풀이 1. 모든 수 탐색 -> TLE(Time Limit Exceeded)

1978번을 활용하여 1보다 큰 수를 is_prime = True로 세팅하고
2, num 범위에서 num을 i로 나눴을 때 나머지가 0이면 소수가 아닌걸로 판명
소수가 아니면 더이상 탐색하지 않고 if문 종료 후 다음 num 탐색
is_prime == True인 경우만 출력한다.

→ 코드 자체는 잘 작동하지만 모든 가능성을 탐색하는 알고리즘이다보니 시간복잡도가 높아 백준에서 시간 초과로 실패하였다.

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

for num in range(m, n+1):
    print(f"현재 num: {num}")
    if num > 1:
        is_prime = True
        for i in range(2, num):
            print(f" - 현재 i: {i}")
            if num % i == 0:
                print(f"{num}은 소수가 아닙니다.")
                print("================")
                is_prime = False
                break

        if is_prime:
            print(f"{num}은 소수입니다.")
            print("================")

    else:
        print(f"{num}은 소수가 아닙니다.")
        print("================")

풀이 2. n의 제곱근 까지만 탐색 -> 시간이 오래 걸리지만 통과!

2번 방법은 n의 제곱근 까지만 탐색하여 1번보다 시간을 단축하는 방법인데,
이게 어떻게 가능하냐면,

어떤 수 N이 소수인지 아닌지 판별할 때, N을 나누는 약수들은 항상 쌍(pair)으로 존재합니다. 예를 들어, 12의 약수는 $(1, 12), (2, 6), (3, 4)$ 처럼 쌍을 이룹니다.

이 약수 쌍의 특징은 다음과 같습니다:

1) 하나의 약수는 항상 N의 제곱근보다 작거나 같고, 다른 하나는 크거나 같습니다.
2) 12의 제곱근은 약 3.46입니다.
3) $(2, 6)$ 에서 2는 3.46보다 작고, 6은 3.46보다 큽니다.
4) $(3, 4)$ 에서 3은 3.46보다 작고, 4는 3.46보다 큽니다.

만약 N이 소수라면, N의 약수는 1과 N 자신뿐이므로 제곱근까지의 범위에서 약수가 발견되지 않고, 만약 N이 합성수라면, N은 반드시 1과 N 사이에 적어도 하나의 약수를 갖습니다.

출처: Gemini

따라서, N이 합성수인지 판별하기 위해 2부터 $\sqrt{N}$ 까지만 나누어 보면 된다. 만약 이 범위 안에 N을 나누는 약수가 없다면, $\sqrt{N}$ 보다 큰 약수도 존재하지 않는다는 의미이므로 N은 소수라고 결론 내릴 수 있다.

풀이 1.과 위에서 언급된 이론을 활용하여 아래와 같이 표현해보았다:

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

for num in range(m, n+1):
    print(f"현재 num: {num}")
    if num > 1:
        is_prime = True
        for i in range(2, int(num**0.5) + 1):
            print(f" - 현재 i: {i}")
            if num % i == 0:
                print(f"{num}은 소수가 아닙니다.")
                print("================")
                is_prime = False
                break

        if is_prime:
            print(f"{num}은 소수입니다.")
            print("================")

풀이 3. 에라토스테네스의 체 -> 빠르게 통과

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 효율적인 방법으로 '체'처럼 소수가 아닌 합성수들을 하나씩 걸러낸다고 해서 붙여진 이름이다. 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다.

동작 원리

소수 목록 준비: 먼저, 2부터 시작하여 찾고 싶은 범위까지의 모든 자연수를 나열한 뒤, 모든 숫자가 소수라고 가정하고 시작한다.
예: 2, 3, 4, 5, 6, 7, 8, 9, 10 ...
배수 지우기: 가장 작은 소수인 2를 시작으로, 2의 배수들을 모두 지우고, 다음으로 남은 숫자 중 가장 작은 소수인 3을 찾아 그 배수들을 지운다. 이 과정을 반복하며, 남아있는 가장 작은 소수의 배수들을 계속해서 지워나간다.
결과 확인: 이 과정을 마치고 남은 숫자들은 모두 소수이다.

핵심 최적화 2가지: 'i'의 제곱근과 'i * i'

에라토스테네스의 체가 효율적인 이유는 불필요한 연산을 최소화하는 두 가지 최적화 때문이다.

범위 제한 (제곱근): 어떤 합성수 N이라도, 그 약수 중 하나는 항상 N의 제곱근보다 작거나 같다. 따라서 소수의 배수들을 지우는 반복문은 N의 제곱근까지만 실행해도 충분하며, 이로 인해 연산량이 크게 줄어든다.
배수 시작점 (i*i): 소수 i의 배수를 지울 때, i2, i3부터 시작하지 않고 i*i부터 시작한다. 그 이유는 i보다 작은 소수들의 배수는 이미 앞에서 지워졌기 때문이다. 예를 들어, 12는 2의 배수를 지울 때 이미 지워졌으므로 3의 배수를 지울 때 다시 검사할 필요가 없다.

아래는 이름은 어렵지만 적용하면 풀이를 쉽게 만들어주는 에라토스테네스의 체를 적용시킨 코드로 범위 제한과 배수 시작점을 설정하여 많은 양을 탐색해야 하는 풀이 1, 2번에 비해 시간이 매우 단축되었다:

# m, n 입력받고
# is_prime 불리언 테이블 만들어주고
# 0, 1은 소수 아니니까 지워주고
# 2부터 n의 제곱근 사이로 탐색하게 틀 만들고
# is_prime = True 일 때, (시작은 0, 1 빼고 전부 True임)
# i*i부터 n+1까지 i배수 탐색하는 틀 만들고
# i배수들은 전부 False 선언해주고
# for문 밖에서 인풋값 범위 내의 is_prime = True 인 i 값 출력


m, n = map(int, input().split())                # 입력값 받기

is_prime = [True] * (n+1)                       # 불리언 테이블 세팅

is_prime[0] = is_prime[1] = False               # 0과 1은 소수가 아니니까 우선 제거

for i in range(2, int(n**0.5) + 1):             # 2부터 n제곱근 사이로 판별할 숫자 범위 정하고                
    if is_prime[i]:                             # 위에서 만든 틀안의 is_prime[True]인 숫자 중
        print(f"\n[ 소수 {i} 발견 ]")
        print(f"  --> {i}의 배수들을 지워나갑니다.")
        for j in range(i*i, n+1, i):            # i*i부터 n+1 사이의 i의 배수를
            print(f"    - {j}은 소수가 아닙니다.")
            is_prime[j] = False                 # 지우고(false 처리하고)


print("--- 최종 결과 출력 ---")
for i in range(m, n+1):                         # m부터 n까지의 i 중,
    if is_prime[i]:                             # is_prime[i] = True이면
        print(i)                                # i(소수로 판명된 수) 출력