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

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

1929번: 소수 구하기

3 16을 예로 들어보자.

3부터 16까지 검사하면서 현재 숫자가 소수이면 출력해주는 구조인데, 그냥 구하면 시간초과가 발생할 것이다. 그리고 1은 좀 특별하게 예외처리를 해주어야 한다. 왜냐?? 1은 소수가 아니지만, 소수 판별 알고리즘에 걸리지 않아 소수로 판별되기 때문이다!

2부터 n의 제곱근까지 i를 증가시키면서 혹시 딱 나눠 떨어지는 수가 있다면, 소수가 아니므로 False를 반환하고, 검사에 걸리지 않았다면 True를 반환해준다.

왜 제곱근까지만 계산해줘도 될까?

100을 예시로 들어보자,  1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10, 20 x 5, 25 x 4, 50 x 2, 100 x 1 으로 분해할 수 있을 것이다.

위와 같이 가운데 10 x 10을 중심으로 같은 연산이 반복된다. 때문에 제곱근(=약수의 중심)까지만 연산을 진행해도 괜찮은 것이다.

import sys
import math
input = sys.stdin.readline

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

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

for num in range(m,n+1):
    if isPrime(num):
        print(num)