[Python] 백준 1929번(소수 구하기) 문제 풀이

 

import math

def is_prime(n):
    if n == 1:
        return False
    if n % 2 == 0:
        if n == 2:
            return True
        return False
    if n % 3 == 0:
        if n == 3:
            return True
        return False
    if n % 5 == 0:
        if n == 5:
            return True
        return False
    if n % 7 == 0:
        if n == 7:
            return True
        return False
    if n % 11 == 0:
        if n == 11:
            return True
        return False
    if n % 13 == 0:
        if n == 13:
            return True
        return False
    if n % 17 == 0:
        if n == 17:
            return True
        return False
    if n % 19 == 0:
        if n == 19:
            return True
        return False
    if n % 23 == 0:
        if n == 23:
            return True
        return False
    if n % 29 == 0:
        if n == 29:
            return True
        return False
    for i in range(30, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

a = list(map(int, input().split()))
for i in range(a[0], a[1]+1):
    if is_prime(i):
        print(i)

 

 막 에라토스테네스의 체 알고리즘 찾아보고, 별 짓을 다 했는데 정답 코드는 이거였다... 소수 판별 함수는 저번에 쓴 글에서 가져온 것을 조금 수정했다. math.sqrt() 로 제곱근을 구해서 했는데, 그 이유는 시간 복잡도를 줄이기 위해서이다. 예를 들어서 16같은 경우에는 약수가 [1, 2, 4, 8, 16] 이고, 25는 [1, 5, 25] 인데, 그러면 약수의 중간값인 1에서 4까지만 보고, 1에서 5까지만 봐도 되지 않겠냐는 것이다. 참신한 아이디어다.

 

 그리고 앞에 조건문들을 썼는데, 그 이유를 모르겠다(과거의 나야, 왜 그랬니.). 방금 조건문이 있는 코드와 없는 코드의 시간 복잡도를 비교해본 결과, 조건문들을 쓰지 않은 코드의 시간 복잡도가 조건문을 쓴 코드보다 1초정도 빠르게 나왔다.

 

 

 

 1부터 1,000,000 까지 코드를 돌려본 결과 조건문이 없는 코드는 약 9.8초, 있는 코드는 10.8초가 나왔다. 코드의 길이도 당연하겠지만 있는 코드는 1120B, 없는 코드는 277B 라는 큰 차이를 보여 주었다. 조건문을 쓰지 않는 편이 좋다.

 

import math

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

a = list(map(int, input().split()))
for i in range(a[0], a[1]+1):
    if is_prime(i):
        print(i)

 

 이 코드가 훨씬 간결하고 빠르다.