BOJ_소수의 연속합_1644 (Java)

문제 링크

성능 요약

메모리: 27144 KB, 시간: 180 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체, 두 포인터

제출 일자

2025년 1월 12일 16:26:31

문제 설명

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

느낀점

• 주어진 수의 범위를 잘 확인하자..
• 예전에 스터디에서 배웠던 에라토스테네스의 체를 최근 두번째 스스로 사용해봐서 뿌듯했다.
• 예제는 맞는데 자꾸 틀리다고 떠서 디버깅이 필요했다. 테케를 직접 만들어서 하려고 했는데 극단적인 수에 대한 답을 알 수 없어서 디버깅이 어려웠다.
• 배열로 소수를 찾는게 너무 오래걸려서 리스트에 저장하는 방식으로 수정했는데, 이때 저장되는 소수의 범위를 n의 범위의 제곱근으로 적용해서 문제가 있었다.

설계 : 15분

• 2부터 4000000까지 순회하며 boolean[]에 해당 숫자가 소수인지 아닌지를 저장한다.
• 작은수부터 차례로 확인할 때, 소수이면 해당 수의 배수를 모두 합성수 처리하고 소수가 아니라면 넘어간다.
• 합성수로는 어떤수를 만들어도 합성수가 되기때문에 이미 앞서 약수에 의해 합성수 처리가 된 수는 넘어가는 것이다.
• 이 과정에서 소수라고 판단된 수들을 리스트에 넣는다.
• 리스트에 차례로 추가된 소수들을 가지고 투 포인터를 통해 연속된 소수들의 합으로 제시된 수를 몇번 만들 수 있는지 경우의 수를 체크한다.
• 위 방법은 최소 2개의 숫자를 더한 경우를 판단하기 때문에 스스로 소수인 경우를 판단하지 못하므로, boolean[] 배열을 통해 제시된 수가 소수라면 answer를 하나 증가시킨다.

코드(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 소수의 연속합_1644
 * Date: 2025.01.12
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static boolean[] isNotPrime = new boolean[4_000_001];
	static List<Integer> primeNum;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		primeNum = new ArrayList<>();
		findPrimeNumber();
		int n = Integer.parseInt(br.readLine());

		int left = 0;
		int right = 1;
		int sum = primeNum.get(left) + primeNum.get(right);
		int answer = 0;
		int size = primeNum.size();

		while (right < size - 1 && left < right) {
			if (sum > n) sum -= primeNum.get(left++);
			else if (sum < n && right < size - 1) sum += primeNum.get(++right);
			else {
				answer++;
				sum += primeNum.get(++right);
			}
		}

		if (!isNotPrime[n]) answer++;

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
		br.close();
	}

	private static void findPrimeNumber() {
		isNotPrime[1] = true;

		for (int i = 2; i <= 4_000_000; i++) {
			if (!isNotPrime[i]) {
				primeNum.add(i);
				int num = i + i;
				while (num <= 4_000_000) {
					isNotPrime[num] = true;
					num += i;
				}
			}
		}
	}
}