[백준 알고리즘][파이썬/Python] 2581번: 소수

문제

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

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

 

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

 

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

입출력 예

 

제출 코드

from math import sqrt

m = int(input()) # start
n = int(input()) # end
sum = 0
min = 0

for i in range(m, n+1):
    if i == 1:
        continue
    elif i == 2:
        sum += i
        min = i
    else:
        for j in range(2, int(sqrt(i))+1):
            if i % j == 0:
                break
        else:
            if sum == 0:
                min = i
            sum += i

if sum == 0:
    print(-1)
else:
    print(sum)
    print(min)

(1) line 3 ~ line 6

m과 n은 문제의 조건에 따라 시작과 끝을 의미하는 변수이며, M이상 N이하의 자연수 중 소수인 수들의 합을 담기 위한 변수 sum, 그 소수값들 중 최소값을 담기 위한 변수 min을 선언한다.

 

(2) line 8 ~ 21

M이상 N이하의 범위이므로 for문의 범위는 (m, n+1)이다. 그 사이를 순회하는 중 i가 1이거나 짝수인 경우, 2인 경우가있을 수 있으므로 해당하는 경우에 대해서는 예외처리를 해준다. 왜 예외처리를 해주는지는 더 아래에 자세히 기술하겠다.

* 참고로 i = 2인 경우에 대한 elif문 다음 i % 2 == 0인 경우도 continue처리를 하여 짝수는 바로 넘어가게끔 제출해봤는데, 시간이나 메모리 측면에서 전혀 이점이 없었다. 물론 m과 n사이의 거리가 매우 크다면 어느 정도 영향을 줄 것이라고 생각하는데, 2581번의 테스트케이스에서는 전혀 영향이 없었다.

1. i = 1일 때
   1은 소수가 될 수 없으므로 바로 다음 수인 2로 넘어가도록 continue를 해준다. 
2. i = 2일 때
   2는 소수를 판별해주는 코드인 line 15 ~ 21에서 지나치게 되어있다. line 15를 보면 for문의 범위가 2부터 '2의 제곱근을 내림한 값 + 1'까지인데, i가 2일 경우 for문의 범위가 (2, 2)가 되므로 for문이 실행되지 않기 때문이다. 하지만 2는 소수이므로 임의로 sum에 2를 반영해주고 min값을 2로 지정해준다.
3.  i가 3 이상일 때
   i를 j로 나눠보며 모든 j에 대해 나머지가 0이 아니라면 i는 소수라는 결론이 나온다. 여기서 j는 2부터 'i의 제곱근을 내림한 값 + 1'까지 해당하는데, 굳이 j를 i - 1까지 올리지 않아도 되는 이유는 소수와 약수의 성질을 확인해보면 쉽게 알 수 있다.
   • 소수는 1과 자기 자신을 제외하고 약수를 가지지 않는다는 성질이 있으며, 약수를 가지는 수는 1부터 자기자신의 제곱근 사이에 약수의 절반을 가지고 있다는 성질이 있다. 하지만 그 나머지 절반은 굳이 알 필요가 없는데, 어떠한 숫자 x는 a * b로 구성되어 있기 때문에 약수 중 더 작은 a를 찾았다면 그 짝이 되는 b는 자연스럽게 찾을 수 있기 때문이다.
   • 위와 같은 성질에 따라 어떠한 숫자가 약수인지 판별하려면 2부터 제곱근까지만 순회하며 해당 숫자들을 나눠보면 되며, 프로그래밍적으로 구현할 수 있게 '제곱근을 내림한 값 + 1'까지 범위를 지정해준다 -> (2, int(sqrt(i)) + 1)

만약 특정 숫자가 소수로 판별되었다면 sum에 해당 숫자를 더해주되, sum이 0이었다면 아직 한 번도 소수가 등장하지 않았다는 것이므로 min값에 해당 숫자를 할당해준다.

 

(3) line 23 ~ 27

'출력'에 대한 설명에서 M이상 N이하의 자연수 중 소수가 없을 경우 -1을 출력하라고 하였기 때문에 sum이 0일 때 -1을 출력하며, 그런 경우가 아니라면 합계와 최소값을 순서대로 출력한다.

 

 

 

Source : https://www.acmicpc.net/problem/2581