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

1929번 (소수 구하기)*

• M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
• 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

import math

n1, n2 = map(int, input().split())

not_sosu = 0
total = 0

sosu_list = []

for i in range(n1, n2+1):
    for j in range(2, int(math.sqrt(float(i)))+1):#제곱근까지만 체크하기
        if(i % j == 0):
            not_sosu += 1
            break
    if(not_sosu == 0):  # 소수라는 뜻
        sosu_list.append(i)
        total += 1
        if(i == 1):
            sosu_list.remove(i)
            total -= 1
    not_sosu = 0

if total == 0:
    print(-1)
else:
    for i in range(len(sosu_list)):
        print(sosu_list[i])

해석

• 제곱근까지만 구해서 시간을 단축한다.

새롭게 알게 된 것

• ** : 제곱근