[백준] 1929 소수 구하기

문제 정보
1. 문제 링크 : 소수 구하기
2. 문제 난이도 : 실버 3
3. 유형 : 수학  

 

1. 첫번째 해결 코드 

메모리 : 32421 kb

시간 복잡도 : 3000 ms

import sys

input = sys.stdin.readline

# m 이상 n 이하의 소수 찾기.
def find_prime_nums(num) :
    if num == 1 : return False
    if num == 2 : return True
    for r in range(2, int(num**0.5) + 1):
        if not (num % r) :
            return False
    return True


m, n = map(int, input().split())
for num in range(m, n+1) :
    if find_prime_nums(num):
        print(num)

 

소수 판별을 위해 for 문으로 나누어떨어지는지를 확인하는 방식으로 구현했다.
1과 2는 예외적인 값이기 때문에 별도의 조건으로 처리하였다.

 

문제 자체는 해결할 수 있었지만,
입력 범위가 커질수록 모든 수에 대해 동일한 연산을 반복한다는 점에서
비효율적인 부분이 눈에 띄었다.

 

 

 

2. 리팩토링 

메모리 : 32421 kb

시간 복잡도 : 1864ms

import sys
input = sys.stdin.readline

def is_prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False

    for i in range(3, int(num ** 0.5) + 1, 2):
        if num % i == 0:
            return False
    return True

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

for num in range(m, n + 1):
    if is_prime(num):
        print(num)

 

리팩토링 과정에서 다음과 같은 개선을 진행했다.

1. 함수명을 find_prime_nums → is_prime으로 수정해 역할을 명확히 했다.
2. 짝수인 경우를 초기에 걸러 바로 return하도록 처리했다.
3. 홀수만 대상으로 소수 판별을 진행하도록 반복문의 범위를 조정했다.

이를 통해 불필요한 연산을 줄일 수 있었고,
결과적으로 연산량을 거의 절반 수준으로 감소시킬 수 있었다.

 

 

3. 에라토스테네스의 체

소수 판별에서 가장 대표적으로 사용되는 알고리즘인
에라토스테네스의 체를 적용해보았다.

 

 

메모리 : 40084 kb

시간 복잡도 : 312 ms

import sys
input = sys.stdin.readline

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

# 0 ~ n 까지 소수 여부 배열 생성
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

# 에라토스테네스의 체
for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

# m 이상 n 이하의 소수 출력
for i in range(m, n + 1):
    if is_prime[i]:
        print(i)

 

이 방식은 처음부터 0 ~ n까지의 소수 여부를 배열로 관리하기 때문에
메모리 사용량은 다소 증가했지만,
사전에 소수를 한 번에 걸러낼 수 있어 시간 복잡도 측면에서 가장 효율적인 풀이였다.

 

 

4. Review

특히 반복적인 소수 판별이 필요한 문제에서는 개별 수를 검사하는 방식보다,
문제의 범위를 먼저 파악하고 알맞은 알고리즘을 선택하는 것이 중요하다는 점을 다시 한 번 느낄 수 있었다.