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

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

프로그래머스

 

주어진 정수 중 3개를 더했을 때 소수가 되는 경우의 수를 구하는 문제이다.

3중 for문으로 간단하게 구현할 수 있다.

 

주어진 구간 내(배열의 크기)에서 각각 3개의 수를 선택하여 더하는 간단한 구조이다.

public int solution(int[] nums) {
        int answer = 0;
        boolean[] isPrime = eratos(2999);

        for(int i = 0 ; i < nums.length-2; i++){
            for(int j = i+1 ; j < nums.length-1; j++){
                for(int k = j+1 ; k < nums.length; k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(isPrime[sum]){
                        answer++;
                    }
                }
            }
        }

        return answer;
    }

 

소수 판별은 에라토스테네스의 체를 이용하여 구하였다.

❗에라토스테네스의 체란? 
구간 내의 모든 소수를 미리 구하는 방식으로, 소수의 배수는 소수가 될 수 없음을 이용하여 소수를 찾았다면 구간 내의 모든 소수의 배수를 미리 지워 구간 내에 소수만 남기는 방식을 말한다.

https://i-am-strong-man.tistory.com/120

[소수] 백준 4134번: 다음 소수 Java

https://i-am-strong-man.tistory.com/69

[정수론] 백준 2581번 - 소수 Java

 

  boolean[] eratos(int max){
        boolean[] isPrime = new boolean[max];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2 ; i*i<=max ; i++){
            if(isPrime[i]){
                for(int j = i*i; j <=max ; j+=i){
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }

 

 

전체코드

import java.io.IOException;
import java.util.Arrays;
class Solution {
  boolean[] eratos(int max){
        boolean[] isPrime = new boolean[max];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2 ; i*i<=max ; i++){
            if(isPrime[i]){
                for(int j = i*i; j <=max ; j+=i){
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }

    public int solution(int[] nums) {
        int answer = 0;
        boolean[] isPrime = eratos(2999);

        for(int i = 0 ; i < nums.length-2; i++){
            for(int j = i+1 ; j < nums.length-1; j++){
                for(int k = j+1 ; k < nums.length; k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(isPrime[sum]){
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
}