백준 1644 소수의 연속합 [자바]

문제 링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

 

문제 접근 :

1. 목적수 이하까지의 모든 소수를 구한 다음 슬라이딩 윈도우를 사용해서 크기를 조정해가며 해당하는 값들을 구한다.

2. 1은 소수가 아니다.

 

팁 : 작은 소수를 구했다면 그 소수를 목적수까지 2,3,4,~ N배를 해주며 예외처리를 해준다. 그러면 자연스레 남은 모든 수들은 소수가 되기 때문에 소수 검출에 시간을 대폭 줄일 수 있다. (i.e. : 에라토스테네스의 체)

 

 

출처 : 위키백과, t.ly/DOio

 

코드 보기

package _0606.ChungLee;
 
import java.io.DataInputStream;
import java.io.IOException;
 
public class BOJ_1644_G3_소수의연속합 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);
 
		byte read() throws IOException {
			if (bufferPos == bufferState) {
				bufferState = dis.read(buffer, bufferPos = 0, bfs);
 
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
 
		}
 
		int nextInt() throws IOException {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
 
	static boolean sosu(int ori) {
		for (int i = 3; i <= Math.sqrt(ori); i += 2) {
			if (ori % i == 0) {
				return false;
			}
		}
		return true;
	}
 
//	빠른 코드
//	public static void findPrimeNumbers() {
//        boolean[] isNoPrime = new boolean[number + 1];
//        int prevPrimeNumber = primeNumbers[numOfPrimeNumbers++] = 2;
//
//        for (int i = 3; i <= number; i += 2) {
//            if (isNoPrime[i])
//                continue;
//            if (prevPrimeNumber + i > number)
//                break;
//            primeNumbers[numOfPrimeNumbers++] = prevPrimeNumber = i;
//            for (int j = i * 2; j <= number; j += i)
//                isNoPrime[j] = true;
//        }
//        if (number > 2 && number % 2 != 0 && !isNoPrime[number])
//            primeNumbers[numOfPrimeNumbers++] = number;
//    }
 
 
	public static void main(String[] args) throws IOException {
		Reader br = new Reader();
		int N = br.nextInt();
 
		int[] arr = new int[400000];
 
		int cnt = 1;
		arr[0] = 2;
		LOOP :for (int i = 3; i <= N + 100; i += 2) {
			for (int j = 3; j <= Math.sqrt(i); j += 2) {
				if (i % i == 0) {
					continue LOOP;
				}
			}
			arr[cnt] = i;
			cnt++;
		}
		// 슬라이딩 윈도우
		int sum = 2, left = 0, right = 0, ans = 0;
 
		while (true) {
			if (sum == N) {
				ans += 1;
				sum += arr[++right];
				sum -= arr[left++];
			} else if (sum < N) {
				sum += arr[++right];
			} else if (sum > N) {
				sum -= arr[left++];
			}
 
			if (arr[left] > N)
				break;
		}
		System.out.println(ans);
	}
}