[프로그래머스 LV1] 소수 만들기

- 문제

- 풀이

class Solution {
    static boolean[] prime;

    public int solution(int[] nums) {
        int answer = 0;

        make_prime();

        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int tmp = nums[i] + nums[j] + nums[k];
                    if (!prime[tmp]) {
                        answer++;
                    }
                }
            }
        }
        return answer;
    }


    public static void make_prime() {
        prime = new boolean[3001];

        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

- 정리

소수만드는건 유클리드 호제법으로 풀었다. 해당 메서드는 make_prime이고 세개의 합이 prime에서 소수인지 확인 후 소수이면 answer++하여 리턴!

[링크] : 개인저장소