[Python] 백준 1929 소수 구하기 - 기본 수학2(4)

백준 1929 소수 구하기
문제

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

입력

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

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

제출

m,n=map(int,input().split())
l=[i for i in range(m,n+1)]
for i in l:
    if i>1: #1제외
        for j in range(2, int(i**0.5)+1): #기존의 (2,i)는 시간 초과
            if i%j==0:
                break
        else:
            print(i)

 

>소수판정 시 제곱근 까지만 확인하는 이유<
N=a*b라고 가정했을 때, a와 b 모두 N의 제곱근 보다 클 수 없다.
따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별 할 수 있다.
예를들어, 16=4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게 된다.

 

예제

3 16

 

결과

백준 1929 소수 구하기

 

1929번: 소수 구하기