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

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

가능한 세 수의 조합을 모두 따져본 뒤 합계가 소수인지 판정만 하면 되는 문제

 

n이 소수인지 판별하기 위해서는 2~n-1까지 모든 수로 나눠볼 필요 없이 루트n까지만 나눠보면 된다.

 

class Solution {
    public boolean isPrime(int n) {
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

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

        // 세 수의 합 구하기
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                for (int k = j+1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (isPrime(sum)) answer++;
                }
            }
        }

        return answer;
    }
}