소수 구하기

문제

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

 

 

 

 문제 해결 

 

위 문제는 소수를 구해야하는 문제이다. 소수를 구할때 구하는 방법이 여러가지가 있지만 무턱대로 for문으로 처음부터 하나하나 나누어서 구하려고 하면 timeout이 나오는 문제이다. 

def point(n) :
    solve = [True] * (n + 1)
    solve[1] = False
    m = n**0.5
    for i in range(2, int(m) +1) :
        if solve[i] == True :
            for j in range( i*i, n + 1, i) :
                solve[j] = False
    return solve

N = int(input())
M = int(input())

solve = point(M)
ans = []
for i in range(N, M+1) :
    if solve[i] == True:
        ans.append(i)

if len(ans) > 0 :
    print(sum(ans), ans[0])
else :
    print(-1)

 

그래서 해결 방법으로 하나의 소수가 발견되면 그 소수에 배수에 해당되는 모든 수를 제외시키는 방법으로 소수를 구하면 시간복잡도를 쉽게 줄일 수 있다.