[알고리즘/Programmers] LV1. 소수 만들기

Programmers LV1. 소수 만들기

 

문제 설명

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

제한 사항

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

 

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

사용 언어

Java

해결 방법

- 3개의 숫자를 갖는 모든 경우의 수(순서X)가 필요하므로 3중 for문이 필요하다.

- 소수를 판별법

1. 2~N 미만의 자연수로 나누어지는 수가 없으면 소수 (solution)
2. 2~루트N 이하의 자연수로 나누어지는 수가 없으면 소수 (solution2)

 

 

코드

/*
    소수 만들기
 */
public class test_12977 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.println(solution(arr));
    }

    // 1. 2~N 이하 자연수로 나누어지는지 판별
    static public int solution(int[] nums) {
        int answer = 0;

        // 서로 다른 3개의 수 조회
        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 num = nums[i]+nums[j]+nums[k];
                    // 소수 판별
                    boolean isSosu = true;
                    for(int a=2; a<num; a++) {
                        if(num%a == 0) {
                            isSosu = false;
                        }
                    }
                    if(isSosu) answer++;
                }
            }
        }

        return answer;
    }

    // 2. 2~루트N 사이의 자연수로 나누어지는지 판별
    static public int solution2(int[] nums) {
        int answer = 0;

        // 서로 다른 3개의 수 조회
        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 num = nums[i]+nums[j]+nums[k];
                    // 소수 판별
                    boolean isSosu = true;
                    for(int a=2; a<=Math.sqrt(num); a++) {
                        if(num%a == 0) {
                            isSosu = false;
                        }
                    }
                    if(isSosu) answer++;
                }
            }
        }

        return answer;
    }
}