[알고리즘]백준 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을 출력한다.

 

풀이

---

특정 범위 내에서 소수를 구하는 알고리즘입니다. 

한 개의 수에 대해서 소수를 판별하는 경우 브루트포스 알고리즘을 통해 

math.sqrt(구하는수)까지 탐색을 하지만, 수의 갯수가 많기 때문에 시간제한을 고려해서 

 

한번에 탐색을 하는, 에라토스테네스의 체 알고리즘을 이용해서 탐색하였습니다. 

 

에라토스테네스의 체의 자세한 내용은 아래 포스팅에서 설명해두었습니다. 

https://kjim.tistory.com/manage/posts/

 

TISTORY

 

 

import sys

M = int(sys.stdin.readline().strip())
N= int(sys.stdin.readline().strip())

def prime_sieve(M,N):
#먼저 전체 범위에 대해서 True인 배열을 만들어줍니다 
    arr =[True for i in range(N+1)]
    arr[0], arr[1]=False, False
    for i in range(2,N+1):
        if arr[i]==True:
#예를들면 2의 경우 4,6 ..등등의 배수 관계에 있는 숫자들은 소수가 아니므로 
#False로 업데이트를 해줍니다 
            j=2
            while i*j<N+1:
                arr[i*j]=False
                j+=1
    return arr  

prime_num = [num[0] for num in enumerate(prime_sieve(M,N)) if num[1]==True and num[0]>=M ] 

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