이번에 풀어본 문제는
백준 1644번 소수의 연속합 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        //N이 1일때
        if(N == 1)
        {
            System.out.print("0");
            return;
        }

        //에라토스테네스의 체
        boolean [] notPrime = new boolean[N+1];
        for(int i = 2; i*i <= N; ++i)
        {
            if(!notPrime[i])
            {
                for(int j = i*i; j <= N; j+=i)
                {
                    notPrime[j] = true;
                }
            }
        }

        List<Integer> primeList = new ArrayList<>();
        for(int i = 2; i <= N; ++i)
        {
            if(!notPrime[i]) primeList.add(i);
        }

        int size = primeList.size();
        int e = 0;
        int sum = primeList.get(0);
        int res = 0;
        for (int start : primeList)
        {
            while (e < size && sum < N)
            {
                e++;
                if(e != size) sum += primeList.get(e);
            }
            if (e == size) break;
            if (sum == N) res++;
            sum -= start;
        }
        System.out.print(res);
    }
}

📝 풀이

입력된 N값을 하나 이상의 연속된 소수를 이용하여 만들 수 있는 경우의 수를 출력하는 문제입니다.
연산에 필요한 만큼의 소수를 primeList에 담아주고, 투포인터를 활용하여 개수를 카운트 해주면 됩니다.
에라토스테네스의 체 방식으로 N까지의 소수를 탐색해주고, 해당 값들을 이용하여 결괏값을 계산했습니다.

투포인터 활용은 이전에 풀었던 문제와 동일하므로 설명은 생략하겠습니다.
수들의 합 2

📜 후기

투포인터를 연습하다가 우연히 에라토스테네스의 체를 접할 수 있었습니다. 이전에 들어보긴 했었는데, 사실 이름부터 조금 난해하게 생겨서 저것까진 몰라도 되겠다~ 하고 넘어갔었는데, 생각했던것 보다 이해하기도 쉽고 유용한 방법인 것 같아요ㅎㅎㅎ 앞으로 소수를 활용하는 문제에서 자주 사용할 것 같습니다!