BOJ 2581 : 소수

문제

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

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

풀이

이전 문제와 동일하지만, 범위를 주고 풀어라는게 추가되었다. 이전 문제와 달리 범위가 있으므로 시간복잡도가 증가하게 되면 시간초과가 의심되었다. 그래서 처음부터 전체 소수의 범위를 줬기 때문에 이를 활용해서 prime_list를 구하고 거기서 범위내에 있는 소수들만 추렸다.

from re import X
import sys

if __name__ == '__main__':
    n = int(input())
    m = int(input())

    prime_list = [2,3]

    for i in range(4, 10001):
        pn = [i % j for j in prime_list]
        if all(pn):
            prime_list.append(i)

    real_data = []
    for x in prime_list:
        if n <= x <= m:
            real_data.append(x)
    
    if len(real_data):
        print(sum(real_data))
        print(min(real_data))
    else:
        print('-1')