boj 1153: 네 개의 소수

이 문제는 미리 1,000,000이하의 소수를 구해두고 bruteforce로 네 개의 소수를 구하다가 시간초과가 발생했는데,

이를 최적화 하는 방법을 생각하지 못해서 결국 다른 블로그들의 풀이를 참고했다ㅠㅠ

골드 바흐의 추측 문제를 풀었었는데도 이러한 방향으로 아이디어를 전혀 떠올리지 못했음..

 

골드바흐의 추측 - 2보다 큰 짝수는 무조건 두개의 소수의 합으로 나타낼 수 있다

1. 미리 1,000,000이하의 소수를 구해둔다.

2. N이 홀수인 경우

• 골드바흐의 추측을 적용하기 위해 이를 짝수로 만들어준다 - 가장 작은 홀수 소수인 3을 뺀다.
• 나머지 짝수를 두개의 소수로 분리한다.

2. N이 짝수인 경우

• 골드바흐의 추측을 적용하기 위해 그대로 짝수로 만들어준다 - 가장 작은 짝수 소수인 2을 뺀다.
• 나머지 짝수를 두개의 소수로 분리한다.

import java.util.*;

public class Main {
	public static int max = 1000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		boolean[] isPrime = new boolean[n + 1];
		calcPrimes(isPrime);

		if (n < 8) {
			System.out.println(-1);
		} else {
			if (n % 2 == 0) {
				System.out.print("2 2 ");
				n -= 4;
			} else {
				System.out.print("2 3 ");
				n -= 5;
			}

			for (int i = 0; i <= n; i++) {
				if (isPrime[i] && isPrime[n - i]) {
					System.out.println(i + " " + (n - i));
					break;
				}
			}
		}
	}

	public static void calcPrimes(boolean[] isPrime) {
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;

		int length = isPrime.length;
		for (int i = 2; i < length; i++) {
			int index = 2;
			while (true) {
				if (index * i >= length) {
					break;
				}

				isPrime[index * i] = false;
				index++;
			}
		}
	}

	public static void print(boolean[] isPrime) {
		for (int i = 0; i < isPrime.length; i++) {
			System.out.println(i + " " + isPrime[i]);
		}
	}

}