G3 백준-1644번: 소수의 연속합

BrokenFinger98·2024년 7월 29일

Problem Solving

목록 보기

2/29

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

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

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

이론

소수란 1과 자기 자신만을 약수로 가지는 수를 말한다.

접근법 1

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

public class Main {
    static int N, ret;
    static ArrayList<Integer> a = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        for (int i = 2; i <= N; ++i) {
            int flag = 1;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) a.add(i);
        }
        for (int i = 0; i < a.size(); i++) {
            int sum = 0;
            for (int j = i; j < a.size() ; j++) {
                sum += a.get(j);
                if(sum == N) ++ret;
                if(sum > N) break;
            }
        }
        System.out.println(ret);
    }
}

제곱근을 이용해서 소수를 판별하고 이중 for문(O(n^2))을 돌려 연속된 소수의 합이 N인 경우의 수를 찾았다.
accept이 나왔지만 더 좋은 알고리즘이 있을거라 생각한다.

Solution

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

public class Main {
    static int N;

    // 해당 인덱스가 소수이면 false, 아니면 true를 저장하는 배열
    // boolean의 default값은 false이기 때문에
    static boolean[] checkPrime;

    // 소수를 저장하는 배열
    static int[] prime = new int[400004];
    static int L, R;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());

        // N까지 소수 일 수 있으므로 N+1 사이즈로 배열 생성
        checkPrime = new boolean[N+1];

        // 0, 1은 소수가 아님
        checkPrime[0] = true;
        checkPrime[1] = true;

        for(int i = 2; i * i <= N; ++i){
            if(!checkPrime[i]){
                for(int j = i + i; j <= N; j += i)
                    checkPrime[j] = true;
            }
        }
		
        // 누적합을 prime배열에 저장
        int k = 1;
        for(int i = 2; i <= N; ++i){
            if(!checkPrime[i]){
                prime[k] = prime[k-1] + i;
                ++k;
            }
        }
		
        // 투포인터 이용해서 연속된 소수의 합이 N인지 판별
        L = 0;
        R = 1;
        int sum = 0;
        int result = 0;
        while (true){
            if(R <= L || R >= k){
                break;
            }
            sum = prime[R] - prime[L];
            if(sum < N) ++R;
            else if(sum > N) ++L;
            else{
                result++;
                ++R;
                ++L;
            }
        }
        bw.write(Integer.toString(result) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}