프로그래머스 - 소수 만들기(java)

문제 설명

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

제한사항

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

import java.util.ArrayList;
import java.util.List;

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

      List<Integer> list = new ArrayList<>();
		
		for(int i=0; i< nums.length; i++) {
			for(int j = 0; j<i ; j++) {
				for(int k=0; k<j ; k++) {
					list.add(nums[i]+nums[j]+nums[k]);
				}
			}
		}
		for(int sum : list) {
           	 answer ++ ;
			for(int i=2;i<sum;i++) {
				if(sum%i == 0) {
					answer --;
					break;
				}
			}
		}

        return answer;
    }
}

 

🎃 나는 소수가 자기 자신과 1 말고는 약수가 없다는 특징만 생각해서 for문안에 범위를 2부터 sum-1까지를 적용했는데

어떤수 sum이 소수가 아니라면, 반드시 √sum 이하의 약수를 가진다는 특성을 적용하면 

i를 2부터 sum-1까지가 아니라 2부터 √sum 까지만 확인하면 충분하다고 한다. 

 

따라서 소수인지 판별해주는 부분을 아래와 같이 변경해주면 된다. 

Math.sqrt()은 Math 클래스에서 제공하는 주어진 숫자의 제곱근을 return 해준다. (double타입으로 return)

for (int sum : list) {
    if (sum < 2) continue; // 2보다 작은 수는 소수가 아님
    boolean isPrime = true;
    for (int i = 2; i <= Math.sqrt(sum); i++) { // i는 2부터 √sum까지
        if (sum % i == 0) { // 약수가 발견되면
            isPrime = false;
            break; // 더 이상 확인 필요 없음
        }
    }
    if (isPrime) {
        answer++; // 소수인 경우 카운트 증가
    }
}