[BOJ][🟡3][백준#01644] 소수의 연속합

문제 출처

BAEKJOON Online Judge #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이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

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

예제

예제 1

입력

20

출력

0

예제 2

입력

3

출력

1

예제 3

입력

41

출력

3

예제 4

입력

53

출력

2

My Sol

import sys
input = sys.stdin.readline

def is_prime(M):
    if M <= 10:
        return base_primes[M]
    for i in range(2, int(M ** (1 / 2)) + 1):
        if not M % i: return 0
    return 1

def next_prime(M):
    while not is_prime(M):
        M += 1
    return M

def make_primes(M):
    l = 0
    arr = [1] * M
    primes = []
    for i in range(2, int(M ** (1 / 2)) + 1):
        if arr[i]:
            l += 1
            primes.append(i)
            for j in range(i * 2, M, i):
                arr[j] = 0

    for i in range(int(M ** (1 / 2)) + 1, M):
        if arr[i]:
            l += 1
            primes.append(i)

    return primes, l

base_primes = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0 ,0]
M = int(input())
primes, l = make_primes(M)

primes.append(next_prime(M))
l += 1

accs = [0]
for p in primes:
    accs.append(accs[-1]+p)

def main(N):
    s, e = 0, 1
    cnt = 0
    while e <= l:
        if s >= e:
            e += 1
            continue

        diff = accs[e] - accs[s]
        # 누적합이 N보다 작은 경우
        if diff < N:
            e += 1

        # 누적합이 N보다 큰 경우
        elif diff > N:
            s += 1

        # 누적합이 N인 경우
        else:
            cnt += 1
            e += 1
            s += 1
    return cnt

cnt = main(M)
if is_prime(M) and primes and primes[-1] < M:
    cnt += 1
print(cnt)

소수 판정과 투포인터를 융합하는 문제였다. 우선 에라토스테네스의 체 알고리즘을 이용해 소수를 판정하는데, 입력된 수 M까지 소수판정을 모두 해주었다.

next_prime 함수를 이용해 M 이후의 소수 하나까지 소수리스트에 추가한 것은 M을 넘긴 첫 소수가 이전 소수와의 합이 M이 되는 경우를 고려한 것이다.

이 소수 리스트가 완성되면, accs 라는 소수 누적합 리스트를 만들고, 시작 인덱스와 끝 인덱스를 나누어 투포인트를 돌리며 값의 차를 M과 비교하며 포인터를 옮겨주면 된다.

이후 M 자체가 소수이며, 소수 리스트의 마지막 값이 M보다 작은 경우에 cnt를 1 추가해준다. 왜냐하면 그 소수 하나 자체가 카운트가 되기 때문

결과

맞았습니다!!

모범답안

출처

import sys

num = int(sys.stdin.readline())


def range_prime(n):
    m = int(n ** 0.5) + 1
    s = [1] * (n + 1)
    for i in range(2,m):
        if s[i] == 1:
            for j in range(i + i,n + 1,i):
                s[j] = 0
    return [i for i in range(2,n + 1) if s[i] == 1]


left, answer, acc = 0, 0, 0
lst = range_prime(num)
for i in range(len(lst)):
    acc += lst[i]
    if acc == num:
        answer += 1
    elif acc > num:
        while acc > num:
            acc -= lst[left]
            left += 1
        if acc == num:
            answer += 1

print(answer)

연산시간은 나보다 소폭 길지만, 문제 풀이가 꽤나 짧은 풀이가 있어 분석하고자 한다.

누적합 리스트는 따로 만들지 않고 매번 소수 리스트의 값을 더하고 빼며 비교하고자 하는 num과 비교 결과를 answer에 추가한다. 인상적인 부분은 매 반복마다 lst[i]를 acc에 더해주며 왼쪽 인덱스를 acc가 num보다 큰 동안 계속 이동시켜 주는 방식을 활용하였다.

그리고 prime list를 return해주는 함수를 list comprehension을 이용해 깔끔하게 작성하셨다. 좋은 로직이라고 생각한다.