백준 1644 소수의 연속합

소수의 연속합 문제보러가기

문제 설명

자바 코드

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

public class Main {
    static List<Integer> primeNumberList=new ArrayList<Integer>();
    static int result=0;
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        primeNumberList.add(2);
        primeNumberList.add(3);
        addPrimeNumberList(N);

        int start=0, sum=0,end=0;
        while(true){
            if(sum>=N) sum-=primeNumberList.get(start++);
            else if(end==primeNumberList.size()) break;//종료조건
            else sum+=primeNumberList.get(end++);
            
            if(sum==N) result++;
        }

        System.out.println(result);
    }

    public static void isDivided(int number){//소수로 나누었을때 떨어지는지 확인
        int x=(int)Math.sqrt(number);
        for (Integer primeNumber:primeNumberList) {
            if(primeNumber>x){
                primeNumberList.add(number);
                return;
            }
            if(number%primeNumber==0) return; //나누어떨어지면 소수가 아님
        }
    }

    public static void addPrimeNumberList(int number){//소수리스트에 추가
        for(int i=5;i<=number;i+=2){
            isDivided(i);
        }
    }

}

문제 풀이

이 문제는 1 ~ N 까지 중 소수가 있는걸 리스트에 담고 sum에  연속적으로 더하면서 N보다 크면 제일 앞쪽에 더했던 소수를 빼면서 값을 체크하면 됩니다.

• 소수 리스트를 구한다.
• 값을 연속적으로 더한다.
• 값이 N보다 크면 제일 앞에 더했던 수를 뺀다.
• 값이 N이랑 같으면 카운트한다.