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

문제:

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

from math import sqrt

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

for i in range(M, N + 1):
    if i == 1:
        continue

    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            break
    else:
        print(i)

코드 설명:

from math import sqrt

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

# M 이상, N이하 만큼 반복
for i in range(M, N + 1):
    if i == 1:
        # 1은 소수가 될 수 없다
        continue

    # 이 방법은 '에토스테네스의 체' 라는 빠른 소수 찾기 방법이다
    # 예를들어 x 이하의 소수를 찾고 싶다고 할 때,
    # x가 2 이상 √x 이하의 수 중에서 하나라도 나누어 떨어지면 그 수는 소수가 아니고
    # 반대로 나누어 떨어지지 않으면 그 수는 소수이다
    # 따라서 2 이상, √N 이하의 수 (= j) 중에서 i와 나누어 떨어지는지 확인한다
    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            # 만약 나눠지면 소수가 아니기 때문에 넘긴다
            break
    else:
        # 소수 출력
        print(i)

 

결과:

??? 5.7초?

분명 문제의 제한 시간은 2초라고 나와있었는데.. 감사하게도 파이썬이라 이해해 주시는 것 같다