[Python] 백준1929 소수 구하기

26 Dec 2022 in Study on Algorithm

백준1929 소수 구하기 링크

문제

예제 입력

---

코드

import sys

m, n = map(int, sys.stdin.readline().split())

for i in range(m, n + 1):
    if i == 1:
        continue
    
    for num in range(2, int(i**0.5) + 1) :
        if i % num == 0 :
            break
        
    else :
        print(i)

설명

파이썬을 통해서 사용자로부터 입력받아 소수 구하기을 구현했습니다. 에라토스테네스의 체를 사용하면 모든 숫자를 검사할 필요가 없으므로(검사해야하는 범위가 클수록 효과적) 시간 복잡도도 O(N) -> O(N^(1/2))으로 감소합니다.

---

정리

import sys

m, n = map(int, sys.stdin.readline().split())

for i in range(m, n + 1):
    cnt = 0
    for num in range(1, i + 1) :
        if i % num == 0 :
            cnt += 1
        if cnt > 2 :
            break
    if cnt == 2:
        print(i)

처음에는 반복문으로 풀어서 시간 초과가 발생했지만 에라토스테네스의 체(2~N의 제곱근까지 탐색)를 활용하면 빠르게 구할 수 있습니다.

---

결과