소수 만들기

문제

주어진 숫자 중 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

답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public int solution(int[] nums) {
       int answer = 0;
       int n = nums.length;
       boolean[] visited = new boolean[n];
       answer = combination(answer, nums, visited, 0, n, 3);        // 3개씩 뽑아야하므로

       return answer;
    }
    
    public int combination(int answer ,int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            int sum = getSum(arr, visited, n);
            
            if(is_prime(sum)){
                answer += 1;
            }
            return answer;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            answer = combination(answer, arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }

        return answer;
    }

    // 조합의 합 출력
    public int getSum(int[] arr, boolean[] visited, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                 sum += arr[i];          // 합계
            }
        }
        return sum;
    }
    
    // 소수인지 확인 
    public Boolean is_prime(int number) {
        // 0 과 1 은 소수가 아니므로 종료
        if(number < 2) {
            return false;
        }

        // 2 는 소수
        if(number == 2) {
            return true;
        }

        for(int i = 2; i < number; i++) {
            // 소수가 아닐경우 종료
            if(number % i == 0) {
                return false;
            }
        }
        // 위 반복문에서 약수를 갖고 있지 않는경우 소수다.
        return true;
    }
}

타임아웃 문제로 인한 소스 수정 (에라토스테네스의 체)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import java.util.*;

class Solution {
    static boolean[] isPrime = new boolean[2997];  // 최대수 1000/999/998 
    static int[] num = new int[3];
    static int[] arr;
    static boolean[] visited;
    static int answer = 0;
    
    public int solution(int[] nums) {
        arr = nums;
        visited = new boolean[nums.length];

        Arrays.fill(isPrime, true);     // 다 true로 채움

        for (int i = 2; i * i < 3000; i++)
            if (isPrime[i])	// 나눠진다면 해당 곱수 다 false로 치환 -> 소수가 아니므로
                for (int j = 2; i * j < 3000; j++)
                    isPrime[i * j] = false;
        
        // 합계 소수인지 구분
        recur(0, 0);
        
        return answer;
    }
    
    static void combination(int depth, int idx) {
        if (depth == 3) {
            if (isPrime[Arrays.stream(num).sum()])
                answer++;
            return;
        }
        for (int i = idx; i < arr.length; i++) {
            if (visited[i]) continue;
            num[depth] = arr[i];
            visited[i] = true;
            combination(depth + 1, i + 1);
            visited[i] = false;
        }
    }
}

에라토스테네스의 체 ??

소수

  • 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
  • 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  • 자기 자신을 제외한 2의 배수를 모두 지운다.
  • 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  • 자기 자신을 제외한 3의 배수를 모두 지운다.
  • 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  • 자기 자신을 제외한 5의 배수를 모두 지운다.
  • 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  • 자기 자신을 제외한 7의 배수를 모두 지운다.
  • 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.