[SWEA] - 5986. 새샘이와 세 소수 (D3)

[문제]

정수론에서, 세 소수 문제란 다음과 같다.
“5보다 큰 모든 홀수는 정확히 세 소수의 합으로 표현될 수 있다. (같은 소수를 합에 사용해도 된다.)”
예를 들어, 7 = 2 + 2 + 3, 11 = 2 + 2 + 7, 25 = 7 + 7 + 11로 나타낼 수 있다.
1939년 러시아 수학자 I. M. Vinogradov는 충분히 큰 홀수는 세 소수의 합으로 표현할 수 있다는 것을 증명했다.
여기서 충분히 크다는 것은 3315 ≈ 107000000 이상의 수라는 의미이다.
현재 가장 발전된 하한은 약 e3100 ≈ 101346 이상의 수이다.
러시아 수학자 I. M. Vinogradov 를 존경하는 새샘이는 직접 세 소수 문제를 풀어보기로 했다.
하지만 이 수는 너무 크기 때문에 컴퓨터로도 이 범위까지의 모든 수를 증명할 수는 없었다.
대신 어떤 크지 않은 홀수에 대해, 세 소수의 합으로 나타낼 수 있는 경우의 수를 구하기로 했다.
5보다 큰 홀수 N을 입력 받아 N = x + y + z (단, x ≤ y ≤ z 이고, x, y, z는 소수) 로 나타나는 경우의 수를 구하는 프로그램을 작성하라.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에 하나의 정수 N ( 7 ≤ N ≤ 999 ) 이 주어진다.
N은 홀수이다.

[출력]
각 테스트 케이스마다 첫 번째 줄에는 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
N을 세 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

문제 풀기

5986. 새샘이와 세 소수

 

---

[풀이]

• 에라토스테네스의 체를 이용하여 list에 2부터 n까지의 소수를 저장한다.
• list에 담긴 수를 꺼내서 더해 n을 만들어 경우의 수를 구한다.

import java.util.ArrayList;
import java.util.Scanner;

class Solution {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			int n = sc.nextInt();
			int cnt = 0;
			ArrayList<Integer> list = new ArrayList<>();
			
			for(int i=2; i<=n; i++) {
				boolean flag = true;
				for(int j=2; j<=Math.sqrt(i); j++) {
					if(i%j == 0) {
						flag = false;
						break;
					}
				}
				if(flag) list.add(i);
			}
			
			for(int i=0; i<list.size(); i++) {
				for(int j=i; j<list.size(); j++) {
					if(list.get(i) + list.get(j) >= n) break;
					
					for(int k=j; k<list.size(); k++) {
						if(list.get(i) + list.get(j) + list.get(k) == n) cnt++;
					}
				}
			}
			
			System.out.format("#%d %d\n", tc, cnt);
		}
	}
}