소수의 연속합1644

LJM·2023년 3월 2일
0

백준풀기

목록 보기
122/259

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

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());

        if(N < 2)
        {
            System.out.println(0);
            return;
        }

        ArrayList<Integer> arrList = new ArrayList<>();

        for(int i = 2; i <= N; ++i)
        {
            if(isPrime(i))
                arrList.add(i);
        }

        int l = 0;
        int r = 0;
        int sum = arrList.get(0);
        int ans = 0;
        while(true)
        {
            if(sum == N)
                ans++;

            if(sum > N)
            {
                sum -= arrList.get(l);
                l++;
            }
            else//sum <= N
            {
                r++;
                if(r >= arrList.size())
                    break;
                sum += arrList.get(r);
            }
        }

        System.out.println(ans);
    }

    public static boolean isPrime(int n)
    {
        if(n < 2)
            return false;

        for(int i = 2; i <= Math.sqrt(n); ++i)
        {
            if(n % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}
profile
게임개발자 백엔드개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN