[Java] 1644번 : 소수의 연속합

[peppermintt0504]

문제 풀이

해당 문제는 범위 내 존재하는 소수 구하기(에라토스테네스의 체)와 투 포인터 알고리즘이 합쳐진 문제이다.

주어진 숫자를 연속된 소수의 합으로 나타낼 수 있는 방법을 구하기 위해 우선 에라토스테네스의 체를 통해 해당 숫자 이하의 모든 소수를 먼저 구한다.

public static int[] getPrime(int num) {
        boolean[] visited = new boolean[num+1];
        visited[0] = true;
        visited[1] = true;

        for(int i = 2; Math.pow(i, 2) <= num; i++) {
            int c = 2;
            while(c * i <= num) {
                visited[c * i] = true;
                c++;
            }
        }

        ArrayList<Integer> nums = new ArrayList<>();

        for(int i = 0; i < visited.length;i++) {
            if(!visited[i]) {
                nums.add(i);
            }
        }
        int[] primes = new int[nums.size()];
        for(int i = 0; i < nums.size();i++)
            primes[i] = nums.get(i);
        return primes;
    }

이후 첫 소수에서 두 포인트로 시작해서 두 포인트 사이의 소수의 합을 숫자와 비교하여 숫자보다 클 경우 왼쪽 포인트를 오른쪽으로, 작을 경우는 오른쪽 포인트를 오른쪽으로 보내면서 소수의 합이 숫자와 같을 경우 answer에 추가해준다.

int left = 0;
int right = 0;

while(right < primes.length) {
    int sum = 0;
    for(int i = left; i <=right; i++) {
        sum+=primes[i];
    }
    if(sum > num) {
        left++;
    }else if(sum < num) {
        right++;
    }else {
        left++;
        answer++;
    }

풀이 코드

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringTokenizer st;
    public static StringBuilder sb = new StringBuilder();
    public static int INF = 100_000_000;
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {-1,0,1,0};

    public static void main(String[] args) throws IOException{
        int num = Integer.parseInt(br.readLine());
        int[] primes = getPrime(num);

        int answer = 0;

        int left = 0;
        int right = 0;

        while(right < primes.length) {
            int sum = 0;
            for(int i = left; i <=right; i++) {
                sum+=primes[i];
            }
            if(sum > num) {
                left++;
            }else if(sum < num) {
                right++;
            }else {
                left++;
                answer++;
            }
        }
        System.out.println(answer);

    }
    public static int[] getPrime(int num) {
        boolean[] visited = new boolean[num+1];
        visited[0] = true;
        visited[1] = true;

        for(int i = 2; Math.pow(i, 2) <= num; i++) {
            int c = 2;
            while(c * i <= num) {
                visited[c * i] = true;
                c++;
            }
        }

        ArrayList<Integer> nums = new ArrayList<>();

        for(int i = 0; i < visited.length;i++) {
            if(!visited[i]) {
                nums.add(i);
            }
        }
        int[] primes = new int[nums.size()];
        for(int i = 0; i < nums.size();i++)
            primes[i] = nums.get(i);
        return primes;
    }
}