[SWEA] 5986. 새샘이와 세 소수

문제

정수론에서, 세 소수 문제란 다음과 같다.

“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는 소수) 로 나타나는 경우의 수를 구하는 프로그램을 작성

 

풀이방법

1) 입력으로 받은 n보다 작거나 같은 소수를 모두 찾는다.

 

2) 이 소수들 중 3개의 수를 뽑아 n을 만들 수 있는 경우의 수를 찾는다.

 

3개의 수만 뽑으면 되는 문제이므로 3중 반복문으로 해결한다. 단, 순열이 아닌 조합이므로 i, j, k 순으로 반복문을 돌릴 때,

i 는 0부터 j는 i부터 k는 j부터 반복한다.

 

소스코드

package samsung;

import java.util.*;

public class s_5986 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			int cnt = 0;
			ArrayList <Integer> a = new ArrayList<>();
			
			for(int i = 2; i <= n; i++) {
				int flag = 0;
				for(int j = 2; j <= Math.sqrt(i); j++) {
					if(i % j == 0) {
						flag = 1;
						break;
					}
				}
				if(flag == 0)
					a.add(i);
			}
			for(int i = 0; i < a.size(); i++) {
				for(int j = i; j < a.size(); j++) {
					if(a.get(i) + a.get(j) >= n)
						break;
					for(int k = j; k < a.size(); k++) {
						int sum = a.get(i) + a.get(j) + a.get(k);
						
						if(sum == n) {
							cnt++;
						}
					}
				}
			}
			
			System.out.println("#" + t + " " + cnt);
		}
	}
}