[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;
	}
}