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

문제설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

My Code

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        int max = nums[len-1]+nums[len-2]+nums[len-3];
        boolean[] primes = new boolean[max+1];
        for(int i=2 ; i<=max/2 ; i++) {
            for(int j=2 ; (j*i)<=max ; j++) primes[i*j] = true;
        }
        return getCount(0, 0, 0, nums, primes);
    }
    public int getCount(int idx, int cnt, int sum, int[] nums, boolean[] primes) {
        if(cnt==3) {
            return !primes[sum]?1:0;
        }
        int ret = 0;
        for(int i=idx ; i<nums.length ; i++) {
            ret += getCount(i+1, cnt+1, sum+nums[i], nums, primes);
        }
        return ret;
    }
}