[백준/파이썬] 2581 소수

📌문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

📌풀이

m, n 사이 자연수 중 1이 포함되어 있다면 1은 소수가 아니므로 판별 제외

m, n 사이 자연수들을 각각 2부터 sqrt(i)로 나눠서 나누어 떨어지는 수가 없다면 소수

 

소수 판별 시 2 ~ i-1가 아닌 2 ~ sqrt(i)까지만 검사하면 충분

 

 

📌코드

import math

m = int(input())
n = int(input())
sum = 0
min = 10001
for i in range(m, n + 1):
    # M이상 n이하의 자연수 중 소수 판별
    if i > 1:  # 1은 소수가 아니기 때문에 판별 제외
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                break
        else:
            sum += i  # 소수의 합
            if i < min:
                min = i
if sum == 0 and min == 10001:
    print(-1)
else:
    print(sum)
    print(min)