I. 소수 만들기

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

1. 문제 설명

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

2. 제한 사항

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

3. 풀이

배열 안의 숫자 3개를 선택해 더하고, 소수인지 판별하는 문제.

결론적으로, 다음과 같이 진행했다.

1. 3중 배열을 사용해, 배열 안의 숫자 3개를 더하는 모든 경우를 반복한다.
2. 3개 숫자의 합 int n을 1부터 n-1까지 나누어 0이 되는 경우가 있는지 확인한다.
3. 0이 되는 경우가 있을 때, 즉시 false를 리턴한다.
4. 0이 되는 경우가 없을 때, true를 리턴한다.

✨소수를 판별하는 method의 최적화는 다음과 같다.✨

1. n이 p*q로 표현될 때 한 수는 항상 n의 제곱근 이하, 다른 한 수는 제곱근 이상이다.
2. n의 제곱근까지만 순회하면, 소수 여부를 판별할 수 있다.

	// O(n^(1/2)) 루트n 시간에 동작하는 소수 판별 알고리즘
	static boolean checkIsPrimeNumber(int num) {
		for(int i=2 ; i*i<=num; i++) {
			if(num%i ==0) {
				return false; //num이 i의 배수면 소수가 아니므로 false
			}
		}
		return true;
	}

4. 소스 코드

class Solution {
    static boolean primecheck(int n){
        for (int i = 2; i < n; i++) {
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
    static 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++) {
                    if(primecheck(nums[i]+nums[j]+nums[k])){answer++;}
                }
            }
        }
        return answer;
    }
}