[백준] 1644 - 소수의 연속합

1. 문제

1644번: 소수의 연속합

2. 개요

어떤 자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

일단 에라토스체네스의 체를 이용해 N까지의 소수를 구한다.

다음 각각 처음과 마지막을 담당할 포인터 두 개를 만든다. 이 둘은 첫 번째 소수부터 시작한다.

또한 연속합을 나타낼 total 변수를 만든다.

처음이 마지막보다 커지거나, 마지막 포인터가 N이하의 소수 개수보다 커질때까지

total에 마지막 포인터가 가리키는 소수를 더한다.

만약 total이 N보다 작다면, r을 1만큼 이동시킨다.

만약 total이 N보다 크다면, l을 1만큼 이동시킨다. 이 때, l번째 소수만큼 total에서 빼주고,

r은 그대로인데 total에는 항상 r번째 소수만큼 더해지고 있으므로 한번 빼준다.

마지막으로 total이 N이라면, 답을 1만큼 늘리면서 l과 r을 모두 1만큼 이동시키고 l번째 소수만큼 total에서 빼준다.

while 문이 종료되었다면 답을 출력한다.

3-2. Python

import sys

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

nums = [i for i in range(N+1)]
primes = []
answer = 0

nums[1] = 0
for i in range(2, N+1):
    if nums[i] == 0:
        continue

    for j in range(nums[i] * 2, N+1, nums[i]):
        nums[j] = 0

    if nums[i] > 0:
        primes.append(nums[i])

l, r = 0, 0
total = 0

while l <= r and r < len(primes):
    total += primes[r]

    if total < N:
        r += 1

    elif total > N:
        total -= primes[l]
        l += 1
        total -= primes[r]

    else:
        answer += 1
        r += 1
        total -= primes[l]
        l += 1

print(answer)

3-3. C#

namespace boj_1644
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] nums = Enumerable.Range(0, N+1).ToArray();
            List<int> primes = new List<int>();

            for (int i = 2; i < N + 1; i++)
            {
                if (nums[i] == 0)
                    continue;

                for (int j = nums[i] * 2; j < N + 1; j += nums[i])
                    nums[j] = 0;

                if (nums[i] > 0)
                    primes.Add(nums[i]);
            }

            int l = 0;
            int r = 0;
            int total = 0;
            int answer = 0;

            while (l <= r && r < primes.Count)
            {
                total += primes[r];

                if (total < N)
                {
                    r++;
                }

                else if (total > N)
                {
                    total -= primes[l];
                    l++;
                    total -= primes[r];
                }

                else
                {
                    answer++;
                    total -= primes[l];
                    l++;
                    r++;
                }
            }
            Console.WriteLine(answer);
        }
    }
}