[백준] 1644번 - 소수의 연속합(Java)

풀이

키워드

• 에라토스테네스의 체

 

  이번 문제는 척 보면 알 수 있듯이 소수를 사용하는 문제이다. 소수하면 바로 에라토스테네스의 체가 떠오른다. 에라토스테네스의 체는 범위 내의 숫자들이 소수인지 아닌지를 미리 판별해내는 계산이다. 간단히 설명하자면, 미리 1~N까지의 배열(boolean)을 만들어 놓는다. 그리고 처음에는 2부터 시작을 한다. 2를 제외한 2의 배수들은 소수가 아니므로 소수가 아니라고 마킹(false)한다. 그리고 다음 숫자 3으로 넘어간다. 3은 소수가 아니라 마킹이 안되었으므로 앞 과정과 동일하게 3을 제외한 나머지 배수들을 소수가 아니라고 마킹한다. 다음 4는 2에 의해 마킹되었으므로 넘어간다. 다음 5는 마킹이 안되었으므로 앞 3과 동일한 작업을 수행한다. 이런 과정을 N까지 반복하면 내가 원하는 숫자 K가 소수인지 아닌지를 바로 판별할 수 있다. (자세한 설명은 밑에 링크 참조)

 

  물론 에라토스테네스의 체를 사용하기 위해서는 메모리 범위를 신경써야 한다. 이번 문제에서 N은 최대 4,000,000이므로 이를 MB로 환산한다면 (4,000,000 / 1024) / 1024 이므로 약 4mb가 나온다. 따라서 에라토스테네스의 체를 사용하기에 충분한 메모리이다. 

 

  소수인지 아닌지 판별된 배열이 있으면 연속된 소수의 합은 구해보기 쉽다. 그냥 2부터 N까지 돌아보면서 소수일 때만 숫자들의 합에 더해주고, 이것이 N과 동일해지면 count를 +1 해주고, N보다 커지면 break해주면 된다.

---

코드

package math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main01 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean [] primes = new boolean[4_000_001];
        
        // 에라토스테네스의 체
		Arrays.fill(primes, true);
		primes[1] = false;
		for (int i = 2; i <= 4_000_000; i++) {
			if (primes[i]) {
				for (int j = i + i; j <= 4_000_000; j += i) {
					primes[j] = false;
				}
			}
		}
		
        // 연속합 구하기
		int count = 0;
		for (int i = 2; i <= N; i++) {
			int total = 0;
			if (!primes[i]) {
				continue;
			}
			for (int j = i; j <= N; j++) {
				if (primes[j]) {
					total += j;
					if (total == N) {
						count++;
					}
						
					if (total >= N)
						break;
				}
			}
		}
		System.out.print(count);
	}
}

---

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

1644번: 소수의 연속합

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전