[백준] 1929. 소수 구하기

1929번: 소수 구하기

---

첫번째 시도: 이전처럼 2부터 n-1까지 모든 수로 n을 나누며 소수를 판별하는 방법을 사용했는데 시간초과가 났다.

두번째 시도: 아래 블로그 글을 참고해 제곱근을 활용하여 2부터 n-1이 아니라 2부터 제곱근까지로 나누어 소수를 판별하도록 알고리즘을 짰다. 

[백준 알고리즘] 백준 1929번 소수 구하기 파이썬(Python)

 

# 1929 소수 구하기 3564ms
# 어떤 수의 제곱근 이하까지만 소수인지 검사하면 제곱근 이상은 검사할 필요가 없다.

def isPrime(m, n):
    for num in range(m, n + 1):
        if num == 1:
            pass

        else:
            sq = math.sqrt(num)
            flag = False
            for i in range(2, int(sq)+1):
                if num % i == 0:
                    flag = True
                    break

            if flag is True:
                continue
            else:
                print(num)

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

 

세 번째 시도: 두 번째 시도가 시간이 다소 걸려서(3564ms), sys 모듈을 활용해 입력받고 따로 함수를 만들어 호출하는 방식으로 코드 리팩토링을 시도했다. 하지만 안타깝게도 시간은 이쪽이 더 걸렸다..(3784ms)

import sys
import math

def isPrime(num):
    if num == 1:
        return

    sq = int(math.sqrt(num))
    for i in range(2, sq+1):
        if num % i == 0:
            return
    print(num)

    return

input = sys.stdin.readline
M, N = map(int, input().split())

for num in range(M, N + 1):
    isPrime(num)