1929 소수 구하기

혀니리리 2022. 8. 16. 15:50

728x90

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

import math

M, N = map(int, input().split())
arr = []
def isPrime(num):
    if num == 1:
        return False
    elif num == 2:
        return True
    else:
        for j in range(2, int(math.sqrt(num)) + 1):
            if num % j == 0:
                return False
        return True
for i in range(M, N+1):
    if isPrime(i):
        print(i)

간단한 문제... 라고 생각했는데 계속 시간초과가 떴다.

이를 해결하기 위해서는 '소수 구하는' 방법을 제곱근까지만 나눠서 증명하도록 해야했다.

그를 위해서는 math.sqrt(num)같은 함수가 있다고 한다.. 알아두자.

728x90