[백준/파이썬] 2581. 소수

https://www.acmicpc.net/problem/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을 출력한다.

 

아이디어

에라토스테네스의 체 를 이용해서 풀어보자 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 : 소수를 판별하는 알고리즘

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형의 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다. 
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

코드

def prime_number(N,M):
    lis = [False,False]+[True for i in range(2,M+1)]
    big = int(M** 0.5) 
    for x in range(2, big+1):
        if lis[x] == True:
            for y in range(x+x , M+1, x) : 
                lis[y] = False


    return [x for x in range(N,M+1) if lis[x]== True]


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


result = prime_number(N, M)

if len(result) !=0:
    sum = 0 
    for r in result: 
        sum += r
    print(sum)
    print(min(prime_number(N, M)))

else : print(-1)

해설

def prime_number(N,M): #인자를 N,M 두 개를 받아서 소수를 판별하는 함수 prime_number 생성 
    lis = [False,False]+[True for i in range(2,M+1)] #[False,False,True,True,True...] 
    # 0,1 은 소수가 아니므로 False값을 넣고, 2부터 M까지는 True 값을 넣은 리스트 lis 생성  
    big = int(M** 0.5) # M 의 최대 약수는 sqrt(n)임 따라서 sqrt(n) 까지 검사, 만약 M이 100이면, 50까지 검사 
    #M까지 모든 수를 검사해봐도 되지만 효율을 위해 M의 제곱근(M의 최대약수)까지만 검사 
    for x in range(2, big+1): #2부터 최대약수 big까지 for문으로 반복 
        if lis[x] == True: #만약 lis[x]의 값이 True 면 
            for y in range(x+x , M+1, x) : #x(1x) 값 자체는 제외하고 x+x(2x)부터 M까지 x(2x,3x,4x,5x,...)만큼 건너뛰면서 값을 False로 바꾼다. 
                lis[y] = False


    return [x for x in range(N,M+1) if lis[x]== True] #for x in range(2,big+1) 반복문을 다 돌고나서 lis[x]값이 True인 경우는 소수인 경우에만 해당한다. 
    #값이 True인 x들만 리스트로 리턴해준다.

 

# 숫자 두 개를 입력받는다. 
N = int(input()) 
M = int(input())

#prime_number 함수의 리턴값 소수 리스트를 result 변수로 받는다. 
result = prime_number(N, M)


if len(result) !=0: #만약 리스트의 길이가 0이 아니면(즉, 해당 범위에 소수가 있으면) 
    sum = 0 
    for r in result: 
        sum += r 
    print(sum) #소수들을 모두 더한 값 출력
    print(min(prime_number(N, M))) #소수 리스트 안에서 가장 작은값(최소값) 출력

else : print(-1) #만약 리스트의 길이가 0이면(해당 범위에 소수가 없으면) -1 출력