[백준] 소수 구하기

문제 링크: https://www.acmicpc.net/problem/1929

 

 

 

오늘의 교훈: 입출력 범위를 잘 보자....

 

소수 구하는 알고리즘은 처음 코딩 걸음마를 하던 시절부터 풀어왔다.

그런데 오늘 문득 든 의문은 이것보다 더 효율적으로 푸는 방법은 없을지 궁금했다.

우선 오늘 푼 방법 먼저 정리하고 효율적으로 풀 수 있는 방법이 있는지 추가로 찾아보자.

 

풀이

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

for x in range(m, n+1):
    isPrime = True if x != 1 else False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0: isPrime = False
    if isPrime: print(x)

 

1. 두 개의 정수를 변수 m, n에 저장한다. -> 최악의 경우 m이 1이면 n만큼 거리가 발생하므로 O(n)

2. 소수를 판별한 변수 isPrime을 정의하고 1이 아닐 때에만 True로 초기화한다. 

3. m 이상 n 이하의 값 x에 대하여, 2부터 제곱근까지 돌며 나누어 떨어지는 값이 있는지 파악한다. -> 가장 큰 값이 n이므로 O(n ・ n^0.5)

 

그럼 내 알고리즘의 시간 복잡도는 O(n ・ n^0.5)이 된다.

저기서 2를 예외 처리를 해 주면 반복문에서 짝수를 제외할 수 있으므로 더 큰 시간을 절약할 수 있다.

그렇게 코드를 짜는 게 코드 가독성을 해칠 것 같아서 굳이 포함시키지 않았다.

 

문제의 입력 범위에 1이 포함되어 있었는데 내가 예외처리를 해주지 않아서 코드가 계속 오답 처리 되었다.

입출력 조건과 문제를 좀 더 꼼꼼하게 보고 푸는 연습을 해야겠다.

 

 

더 배우고 싶은 점

소수를 효율적으로 구하는 방법을 찾아보니 "에라토스테네스의 체"가 나왔다. 정말 오랜만에 듣는 이름이다.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity 에 따르면 이 방식으로 소수를 구하면 O(n log log n) 이라고 한다. 뭔가 요상한 시간 복잡도라 어떻게 전개되는지 더 궁금하다.