[lv2] 2581. 소수(Python 파이썬 풀이)

출처

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

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을 출력한다.

예제 입력 1

60
100

예제 출력 1

620
61

예제 입력 2

64
65

예제 출력 2

-1

예제 입력 3

1
4

예제 출력 3

5
2

해석

주어진 두 구간 사이에 존재하는 소수들의 합을 구하면 되는 문제이다. N과 M은 10000이하이기 때문에 1부터 M까지의 숫자에 대해서 소수를 판별하고 최종적으로 N과 M사이에 존재하는 소수들의 합을 구할 것이다. 소수를 판별 하는 방법은 2부터 M의 제곱근까지 정수들은 자신을 제외한 배수들이 소수가 아니다는 것을 활용하도록 한다. 비슷한 방법으로는 에라토스테네스의 체를 활용하시면 됩니다. 예를 들어 소수 2에 대해서 생각해본다면 2를 제외한 2의 배수들은 모두 소수에서 배제를 시키는 것이다. 그렇게 1부터 M까지의 숫자들을 일일이 소수인지 판별하고 다시 N부터 M까지의 숫자들 중에서 소수인 것들을 리스트에 담아서 리스트의 합과 가장 처음에 나온 값을 출력해주면 됩니다.

소스 코드

import sys
 
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
ba = []
vi = list(True for _ in range(10001))
vi[1] = False
for i in range(2,int(m**(1/2))+1):
    for j in range(2*i, 10001, i):
        if vi[j]:
            vi[j] = False
for i in range(n, m+1):
    if vi[i]:
        ba.append(i)
if ba:
    print(sum(ba))
    print(ba[0])
else:
    print(-1)