[백준 2581번]Python 풀이

너어어엉어어어무 오랜만에 쓴다.

그간 이래저래 바빴다. 아쉽게도 더이상 바쁘지 않다.

 

아무튼 심심함을 잊기위해 문제풀이를 하다 좀 재밌는문제라 가져왔다.

 

풀이위주로 설명할 것이고, 코드는 일부러 맨 하단에 두겠다.

 

당연하게도, 이렇게 글이 올라왔단건 흥미로운 계산방법이 있다는뜻

 

요약하면, 두 수를 입력받아 두 수를 포함한 범위 내에있는 소수의 합과 그 소수들 중 제일 작은값을 출력하라는건데

소수 (수론) - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

소수 (수론) - 위키백과, 우리 모두의 백과사전

보통 알고있는 소수가 맞다. 2,3,5,7,11...이정도는 알고 있지만 문제를 푼 후 정확한 검증을 위해 위키에 가서 찾아봤다.

 

풀이방식은 늘 그렇듯 여러가지인데,

 

소수의 특성 자체를 고려해서 % 연산자를 이용해서 걸러줄 것이냐?

혹은 동적계획법에서 했던것처럼 입력된 값에서 걸러주는 식으로 할것이냐? 고민이 되었다.

 

일단 첫번째 방법으로 실행했을때, 값을 제법 정확히 나왔는데... 음.. 아무튼 그건 버렸고

동적계획법 풀듯 풀어보았다.

 

우선 리스트에 의미를 부여해줬다. boolean형이든 int형이든 무엇이든 본인이 의미만 부여해주면 된다.

예로들어 Y/N , 1/0 , True/False 등

난 2,3번째 둘 다 사용했다. 그래서 정답이 두개다.

 

일단 풀이를 위해 초기화를 진행해야한다.

lst = [True for _ in range(end+1)] 이런식으로 최대값을 포함해야해서 +1까지 써주었고, 0번지와 1번지는 False로 세팅한 후 반복문을 실행했는데

 

여기서 분명 최근 귀에 박히도록 들은 유클리드의 또 다른 공식이 있나 찾아보았다.

하지만 이 양반이 소수에 관해 기록한건 딱히 없었고, 대신 에라토스테네스라는 고대 그리스 수학자의 공식을 이용했다.

 

일명 에라토스테네스의 체 라고해서, 어떤 방식으로든 n~m까지의 숫자가 있다고 쳤을때, 그 사이의 숫자들간 계산을 했을때 해당 값이 나오면 따로 처리를 하는 방식이다.

 

쉽게 말하면, 시작값은 1, 끝값은 100이라고 가정을 했을때,

1은 소수가 아니니 false세팅이 되었을거고, 2부터 시작해서 어떠한 변수 x를 곱해주는것이다.

이 경우 2의 배수를 곱했다. (하지만 내 실제 계산방식은 이와 약간 다르다.)

그렇게 2의 배수들의 인덱스 4면 4번인덱스 이런식으로 걸러서 그곳을 False로 변경해준다.

그렇게 end값까지 돌아준 후 곱한 값이 end를 넘으면 indexError가 나므로 곱한값이 end를 넘으면 값을 올려준다.

3이 True이므로 3도 배수들을 전부 False로 세팅

4는 2의 배수이므로 이미 세팅되어있기에 pass

5는 True이므로 5의 배수들 False로...

 

이런식으로 계산하는것인데, 하나 착오를 한 부분은 2~9까지 값으로만 계산이 되는 경우만을 생각해버려서

11 * 11 = 121 이런수도 소수로 처리하는 오류를 범했다.

 

때문에 기존엔 곱해주는 두 수중 하나의 수만 end까지 돌았다면, 이젠 두 수 모두 end까지 돌게했다.

 

그렇게 처리하니까 정답이 떴다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

사실 별거 없다. 

요약하자면,

1. start ~ end까지의 배열을 어떤 형식으로든 초기화해준다.

2. 첫번째 for문으로 각 수의 배수들을 전부 소수가 아님을 표기해준다.

3. 2번을 계속 반복한 후 for문으로 소수들만 걸러줄건데, 첫번째로 들어오는 소수를 minimumPrimeNumber로 저장해주고, sumPrimeNumber에 값을 계속 쌓아준다.

4. 출력시 sumPrimeNumber가 0이면 -1이 출력되도록한다. 소수 중 가장 작은 수는 2인데, 0은 아예 계산조차 안됐다는 애 즉 전부 False라는 뜻

 

 

반례

1 , 1

= -1

 

 

코드 주의

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

import sys

def eratos(start,end):
    checkLst = [True for _ in range(end+1)]
    checkLst[0] = False
    checkLst[1] = False
    sumData = 0
    minimumData = 0
    for i in range(2,end+1):
        for j in range(2,end+1):
            if i*j >= end+1:
                break
            checkLst[i*j] = False

    for i in range(start,end+1):
        if sumData == 0:
            minimumData = i
        if checkLst[i] == True:
            sumData += i

    if sumData != 0:
        print(sumData)
        print(minimumData)
    else:
        print("-1")

def main():
    start = int(sys.stdin.readline())
    end = int(sys.stdin.readline())
    eratos(start,end)


main()