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

https://programmers.co.kr/learn/courses/30/lessons/12977?language=java 

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

 

소수 알고리즘을 활용해서 계산하는 문제.

약수의 성질을 이용해서 2부터 주어진 수의 제곱근까지 확인만 하면 된다.(성능 개선)

약수의 성질?

- 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭적인 구조

- ex) 16의 약수는 1, 2, 4, 8, 16 => 1 x 16, 2 x 8, 4 x 4

- 그러므로 특정한 자연수의 모든 약수를 찾을 때 가운데까지만 확인하면 됨.

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

        // 3가지 조합이니 3번 돌림
        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++) {
                    if(isPrimeNumber(nums[i] + nums[j] + nums[k])) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
    // 약수 체크
    public boolean isPrimeNumber(int v) {
        for(int i = 2; i <= Math.sqrt(v); i++) {
            if(v % i == 0) {
                return false;
            }
        }
        return true;
    }
}