[Programmers]-소수 만들기

문제

숫자들이 담겨있는 배열에서 3개의합이 소수인 갯수를 반환하면되는 문제이다.

코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int N = nums.length*1000;
        boolean[] notPrime = new boolean[N+1];
        
        notPrime[0] = notPrime[1] = true;
        
        for(int i=2;i*i<=N;i++){//에라토스테네스
            if(!notPrime[i]){
                for(int j=i*i;j<=N;j+=i){
                    notPrime[j] = true;
                }   
            }
        }
        
        int n = nums.length;
        for(int i=0;i<n;i++){//3개의합
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    if(i==j||k==i||k==j) continue;//중복이 없어야한다.
                    
                    int sum = nums[i]+nums[j]+nums[k];//합
                    if(!notPrime[sum]) answer++;
                }
            }
        }
        
        return answer;
    }
}

코드 설명

에라토스테네스 채를 이용해서 소수인지 아닌지 판별하는 배열을 만들어 구한다. 그리고 합이 소수인지 아닌지 판별한다.

요약

• 에라토스테네스의채로 쉽게 구하자