백준 1929번 소수 구하기 파이썬

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

답안

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

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

---

 

소수 구하는 문제를 구현하는 건 쉽다.

문제가 정답률이 낮은 이유는 아마 시간 초과 때문이라고 생각한다.

이 문제를 봤을 때 학교에서 이산수학 강의에서 배운 내용이 생각났다.

101이 소수인지 증명하라는 문제였는데 결론만 말하면

루트(101) 보다 작은 소수 2, 3, 5, 7로 안 나눠지면 소수이다.

그래서 else 절에

for i in range(2, int(n**0.5) + 1):

 

이렇게 짠 것이다.

정수 제곱근을 활용하지 않고 무작정 돌리다 보면

최대의 경우 n이 100만이기 때문에 시간 복잡도가 오래 걸린다.