프로그래머스 소수 만들기

문제

programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

 

풀이

에라토스테네스의 체 를 이용하여 미리 소수들을 구해놓습니다.

숫자들의 합을 구하고 해당 인덱스로 가서 소수가 맞는지 확인합니다.

이전 포스팅의 소수 문제를 먼저 풀고오시면 좋습니다.

 

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

        int[] arr = new int[3000];  //0:소수 , 1:소수X
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i < 3000; i++) {
            for (int j = i + i; j < 3000; j += i) {
                arr[j] = 1;
            }
        }
        // arr 소수 거르기 완료

        int len = nums.length;
        for (int i = 0; i < len; ++i) {
            for (int j = i + 1; j < len; ++j) {
                for (int k = j + 1; k < len; ++k) {
                    if (i == j || i == k || j == k) continue;
                    if (arr[nums[i] + nums[j] + nums[k]] == 0) ++answer;
                }
            }
        }

        return answer;
    }
}