[파이썬] 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

---

특정 범위 내에서 소수를 찾는 문제는 왠만하면 에라토스테네스의 체 를 사용하자.

 

먼저 리스트를 만들어 입력받은 범위 내의 숫자를 다 넣는다.

 

그리고 에라토스테네스의 체 를 사용하여 소수가 아닌 수들을 리스트에서 제거한다.

 

이후 리스트가 비어있다면(소수가 없다면) -1을 출력하고, 그게 아니라면 조건에 맞게 출력한다.

 

---

import math
def solve(a, b):
    resultList = list(range(a, b+1))

    #1은 소수가 아니므로 있다면 제거하자.
    if 1 in resultList:
        resultList.remove(1)

    #에라스토스테네스의 체 사용
    for i in range(2, math.ceil(math.sqrt(b))):
        for temp in resultList:
            if temp/i==1:
                pass
            elif temp%i==0:
                resultList.remove(temp)

    #범위 내에 소수가 없다면 -1 반환
    if not resultList:
        return -1
    else:
        sum = 0
        for i in resultList:
            sum += i
        min = resultList[0]

        return "{}\n{}".format(sum, min)


if __name__ == "__main__":
    a = int(input())
    b = int(input())
    print(solve(a, b))