[프로그래머스] 소수 만들기

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

프로그래머스

---

 

nums의 원소는 1부터 1000사이의 자연수이므로, nums에 있는 서로 다른 세 수의 합은 최대 3000이 될 것이다.

-> 1부터 3000 사이의 수들을 전부 소수인지 판별해놓는다 (에라토스테네스의 체 이용)

 

nums의 서로 다른 세 원소의 합이 소수인지 체크하여 정답을 구한다

---

java

class Solution {
    public int solution(int[] nums) {

        boolean[] primeNumbers = new boolean[3001];
        primeNumbers[0] = false;
        primeNumbers[1] = false;
        for(int i=2; i<3001; i++){
            primeNumbers[i] = true;
        }
        for(int i=2; i*i<3001; i++){
            if (primeNumbers[i]){
                for(int j=i*2; j<3001; j+=i){
                    primeNumbers[j] = false;
                }
            }
        }
        
        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++){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(primeNumbers[sum]) answer++;
                }
            }
        }
        return answer;
    }
}