[level1] 프로그래머스 - 소수만들기(JAVA)

- 전역변수로 Eratos[]라는 소수인지를 저장할 배열을 만들어 두었다. => 에라토스테네스체 

에라테네스의 체의 원리는 다음과 같다.

- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
- 2는 소수이므로 소수처리
- 남아있는 수에서 자기 자신을 제외한 2의 배수를 모두 지움
- 남아있는 수 가운데 3은 소수이므로 소수 처리 후 3의 배수를 모두 지움
- 남아있는 수 가운데 5은 소수이므로 소수 처리 후 5의 배수를 모두 지움

위의 과정들을 반복하면 구하는 구간의 모든 소수가 남는다. 1~n 구간의 소수를 찾고 싶은 경우, t^2>n을 만족하는 t보다 작은 배수만 지워도 됨

  ex) 1~120이면, 11^2>120 이므로, 11보다 작은 수 배수들만 처리해주면 됨

t보다 작은 배수를 지우고 남은 수는 모두 소수!!

 

 

- 조합(combination)함수에서 숫자 3가지를 선택한 후, 

   그 세 수의 합(sum)이 Eratos에 true인지를 확인 하여 answer을 증가시켜주었다.

 

 

package com.pro.level1;

import java.util.Arrays;

public class 소수만들기 {

	public static void main(String[] args) {
		int[] nums = { 1, 2, 7, 6, 4 };
		System.out.println(solution(nums));
	}

	static int answer;
	static boolean Eratos[];

	public static int solution(int[] nums) {
		// 소수인 것 찾기 => 에라토스테네스의 체
		Eratos = new boolean[3001];
		Arrays.fill(Eratos, true);	// 일단 모두 소수라고 해두고
		for (int i = 2; i * i <= 3000; i++) {
			if (Eratos[i])
				for (int j = i * i; j <= 3000; j += i)
					Eratos[j] = false;	// 아닌 것을 하나씩 지운다.
		}

		combination(0, 0, 0, nums);

		return answer;
	}

	// 3개씩 고르는 경우의 수
	private static void combination(int cnt, int cur, int sum, int[] nums) {
		if (cnt == 3) {
			if (Eratos[sum] == true)
				answer++;
			return;
		}

		for (int i = cur; i < nums.length; i++) {
			combination(cnt + 1, i + 1, nums[i] + sum, nums);
		}
	}
}