LV1. 소수 만들기

문제 설명

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

제한사항

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

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

알고리즘은 간단했다.

배열 내에서 3개의 원소를 완전 탐색으로 결정하였다. 그 후 3개의 원소를 택할 때마다 소수를 판별하는 findnum메소드를 통해 소수인지 아닌지를 판별하였는데, 이 문제의 관건은 소수를 얼마나 효율적으로 빨리 판별하는지와, 배열 내에서 3개의 원소를 어떻게 선택할 것인지이다.

우선, 소수는 1과 자기 자신만을 약수로 갖는데, 2부터 판별하고자 하는 수의 제곱근까지의 자연수들로 내가 판별하고자 하는 수와 나누어 주어서 나누어 떨어지지 않으면 된다.

예를 들어 16이라는 수는
1 16
2 8
4 4
8 2
16 1
인데, 4 4 이후로는 굳이 안해도 되는 과정이므로 16의 제곱근인 4까지만 test해보면 된다.
이 test를 진행하는 동안 나누어 떨어지는 수가 있다면, 소수가 아니고 나누어 떨어지는 수가 없다면 소수이다!!

내가 작성한 코드

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        
        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 total = nums[i] + nums[j] + nums[k];
                    if(findnum(total)==0){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
    
    public int findnum(int tot){
        int cnt=0;
        for(int a=2;a<=Math.sqrt(tot);a++){
            if(tot%a==0){
                cnt++;
            }
        }
        
        if(cnt>=1){
            return -1;
        }
        else{
            return 0;
        }
    }
}```