[백준/Python] 1929: 소수 구하기

[백준/Python] 1929: 소수 구하기

m과 n이 입력으로 주어질 때, m 이상 n 이하의 소수를 모두 출력하는 문제이다. 문제 자체는 간단한데 isPrime 함수에 n == 1일 시 False를 리턴해야 한다는 점을 빼먹어서 틀렸다.

소수는 1과 자기 자신만으로 나누어지는 수다. 간단한 상식이지만 배운지 너무 오래돼서 까먹는 경우가 많은데 1은 소수가 아니다.

소수인지 아닌지를 판별하기 위해선 2부터 n까지 나누어 보면 되는데, 이때 n까지 전부 나누어 볼 필요는 없고 $\sqrt{n}$까지만 나누어 보아도 충분하다. 왜냐하면 $\sqrt{n}$ 이상의 수로 n을 나누어 보아도 어차피 0으로 나누어 떨어지는 일이 없기 때문이다. 아마 n까지 전부 for문을 전부 돌려보면 시간 초과가 날 것이다.

소스코드

def isPrime(n):
    if n == 1:
        return False
    for i in range(2, int(n**(1/2)) + 1):
        if n%i == 0:
            return False
    return True

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

for i in range(m, n+1):
    if isPrime(i) == True:
        print(i)

(참고) 풀이와 별로 상관은 없는 특이점 : 백준에서 채점 우선순위가 2인 문제라 트래픽이 많은 경우 몇분 기다려야 채점이 된다.