[BOJ] 1644 소수의 연속합

date

Jul 17, 2023

slug

boj-1644

author

status

Public

문제 링크

https://www.acmicpc.net/problem/1644

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)

41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)

53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

문제풀이

에라토스 테네스의 체를 통해서 n이하의 소수를 모두 구해주고

그 소수들로 이루어진 리스트를 만든다.

투포인터를 사용해 첫 포인터는 0번째 인덱스

마지막 포인터는 1번째 인덱스에서 시작하게 하여

첫~마지막의 합이 n보다 작으면 마지막 포인터의 인덱스를 증가

why? 마지막 포인터를 증가시켜 만든 연속의 합은 항상 이전의 것보다 크다.

n보다 크면 첫 포인터의 인덱스를 증가시킨다.

why? 첫번째 포인터를 증가시켜 만든 연속의 합은 항상 이전의 것보다 작다.

만약 첫~마지막 합이 같으면 카운트를 하나 더해주고

첫번째와 마지막까지의 조합으로는 더이상 못하므로

두 포인터의 인덱스를 하나씩 증가시켜 다시 탐색을 시작한다.

그렇게 계속탐색을하다보면 두 포인터의 구간이 항상 n보다 큰 구간이 오게되는데

그때 두 포인터가 만나게 된다. 더이상 연속합으로는 소수를 구할 수 없다. 종료

파이썬 문제풀이 코드


N = int(input())

arr = [1] * (N+1)
arr[1] = 0
def function(): # 에라토스테네스의 체
    for i in range(2, int(N**0.5)+1):
        if arr[i] == 0:
            continue
        for j in range(2*i, N+1, i):
            arr[j] = 0
function()            
# print(arr)
prime_list = [i for i in range(2, len(arr)) if arr[i] == 1 ] # O(n)
# print(prime_list)
first_pointer = 0
end_pointer = 1
count = 0 if arr[N] != 1 else 1
while True:
    target = sum(prime_list[first_pointer:end_pointer+1])
    if first_pointer == end_pointer or N <= 4:
        break
    if  target < N:
        end_pointer +=1
    elif target > N:
        first_pointer += 1
    else:
        count+=1
        first_pointer +=1
        end_pointer += 1
     
print(count)

시간복잡도

https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

[BOJ] 1644 소수의 연속합

문제 링크

문제

문제풀이

입력

출력

예제 입력

예제 출력

알고리즘 분류