[Python] 1644번 : 소수의 연속합

문제 3줄 요약

1. 연속된 소수의 합으로 자연수를 나타내고자 한다.

2. 위의 예시는 연속된 소수의 합으로 나타낼 수 있지만, 20과 같이 연속된 소수의 합으로 나타낼 수 없는 경우도 있다.

3. 주어진 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수는?

 

 

 

입력이 최대 400만이었다.

먼저 든 생각은 400만 이하의 자연수 중에 소수는 몇 개이고,

어떻게 구해야하나..?

 

문제의 카테고리가 정수론인만큼

정수론의 에라토스테네스의 체를 참고하였다.

 

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체 - 나무위키

 

짧게 설명해보자면,

전체 숫자에서 2의 배수, 3의 배수, ···, x의 배수를 전부 지워가며,

남는 숫자들을 소수로 판별하는 방식이다. 

 

위의 문서 중 

 

일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만,
특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법이 없다.

라는 문구를 볼 수 있다.

 

즉, 에라토스테네스의 체와 투포인터를 이용하여

주어진 자연수와 같은 순서의합을 찾는다.

 

 

from sys import stdin

if __name__ == "__main__":
    N = int(stdin.readline())
    answer = 0
    #에라토스테네스의 체
    eratos = [0]
    Max = 4000001
    
    # 소수 판별
    check = [True] * Max
    check[0],check[1] = False,False

	# 에라토스테네스의 체를 이용한 범위 내 소수 판별
    for num in range(2,Max):
        if check[num] == False:
            continue
        eratos.append(eratos[-1]+num)

        remove = 2
        while num * remove < Max:
            check[num*remove] = False
            remove += 1

    Left,Right = 0,1

	# 투포인터를 이용한 N과 같은 소수의 합 찾기
    while(Right < len(eratos)):
        sum = eratos[Right] - eratos[Left]
        if sum < N:
            Right += 1       
        elif sum == N :
            answer += 1
            Right += 1
        elif sum > N:
            Left += 1

    print(answer)

 

소수를 구할 때,

미리 순서대로 합을 구해 투포인터를 이용한 값 찾기에서는

빼주는 방식으로 N과 같은 자연수를 찾아주었다.

 

해당 문서에 써있는 에라토스테네스의 체 설명처럼

프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시인 문제였다.

 

끝!