[BOJ] 1644 소수의 연속합 - JAVA

1. 문제

1644번: 소수의 연속합

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

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과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  N까지의 소수를 구하면서 따로 list에 소수를 모아놓는다. 소수 구하는 방식은 에라토스테네스의 체를 사용했다.

2.  왼쪽을 기준으로 시작하는 반복문을 만들어서, 그 수부터 옆으로 하나씩 더해가면서 sum을 구했다. sum이 N과 동일하면 answer을 하나 더한다. 그리고 sum이 N보다 크거나 "같다면" 반복을 멈춘다.

3.  마지막으로 answer을 출력한다.

import java.io.*;
import java.util.*;
 
public class BOJ_1644_소수의연속합 {
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
 
      // N까지의 소수 구하기 + 리스트에 모으기
      boolean[] prime = new boolean[N + 1];
      prime[0] = prime[1] = true;
      ArrayList<Integer> primeList = new ArrayList<>();
      for (int i = 2; i <= N; i++) {
         if (prime[i]) continue;
         primeList.add(i);
         for (int j = i+i; j <= N; j += i) {
            prime[j] = true;
         }
      }
 
      //소수만 있는 합 구하기
      int answer = 0;
      int sum;
      for (int left = 0; left < primeList.size(); left++) {
         sum = 0;
         for (int right = left; right < primeList.size(); right++) {
            sum += primeList.get(right);
            if (sum == N) answer++;
            if (sum >= N) break;
         }
      }
 
      //출력
      System.out.println(answer);
   }
 
}

---

3. 결과

다른 방식으로 여러번 풀이 시도해봤다. 

위에서 첫번째는 sqrt를 변수에 저장해서 사용했던 코드,

위에서 두번째는 Scanner사용 코드

세번째는 sqrt쓴 코드(변수저장x)

네번째는 sqrt 잘못쓴 코드

다섯번째는 그냥 다른 방식으로 풀었던 코드

마지막이 본문이다~