[백준] 1644번: 소수의 연속합 (C++, JAVA)

문제 링크

1644번: 소수의 연속합

---

간단하게 소수 복습을 할 수 있는 문제입니다!

사실 오랜만에 소수 문제를 풀려니, 에라토스테네스의 체를 까먹어버려서(...)

전에 풀었던 소수 문제를 참고해서 문제를 풀었습니다. 복습이 되서 좋았습니다.

풀이

간단하게 소수(정수론) + 투포인터로 풀이가 가능합니다.

1. MAX(`4000000`)까지의 소수를 모두 구해줍니다.
2. 투포인터를 활용해서 부분합을 구한 뒤, 제시된 N과 부분합이 일치한다면 결과값+1 을 해줍니다.

풀이코드

C++ 풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

const int MAX = 4000001;
bool prime[MAX];

void solve() {
  int n;
  cin >> n;

  
  fill(prime + 2, prime + MAX, true);
  for (int i = 2; i * i < MAX; i++) {
    if (!prime[i]) continue;
    for (int j = i * i; j < MAX; j += i) {
      prime[j] = false;
    }
  }

  int cnt = 0;
  int en = 2;
  int sum = 0;
  for (int st = 2; st < n; st++) {
    if (!prime[st]) continue;
    while (en < n and sum < n) {
      if (prime[en]) sum += en;
      en++;
    }
    if (en == n) break;
    if (sum == n) {
      cnt++;
    }
    sum -= st;
  }
  if (prime[n]) cnt++;
  cout << cnt;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

JAVA 풀이코드

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

class Main {
    static final int MAX = 4000001;
    static boolean[] prime;
    private static void solve(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        prime = new boolean[MAX];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i < MAX; i++) {
            if (!prime[i]) continue;
            for (int j = i * i; j < MAX; j+=i) {
                prime[j] = false;
            }
        }
        
        int cnt = 0, sum = 0;
        int en = 2;
        for (int st = 2; st < n; st++) {
            if (!prime[st]) continue;
            while (en < n && sum < n) {
                if (prime[en]) sum += en;
                en++;
            }
            if (en == n) break;
            if (sum == n) cnt++;
            sum -= st;
        }
        if (prime[n]) cnt++;
        res.append(cnt);
    }

    private static StringBuilder res;
    public static void main(String args[]) throws Exception {
        if (args.length > 1) fileInputOutput(args[0], args[1]);
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            res = new StringBuilder();
            solve(br);
            bw.write(res.toString());
        }
    }

    private static void fileInputOutput(String inputPath, String outputPath) throws IOException {
        System.setIn(new FileInputStream(inputPath));
        System.setOut(
            new PrintStream(
                new BufferedOutputStream(
                    new FileOutputStream(outputPath)
                )));
    }
}

배운점

• 에라토스테네스의 체를 복습할 수 있었습니다.
• 투포인터 방식의 패턴을 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!