소수 만들기

문제 : 소수 만들기

풀이

public static boolean[] prime = new boolean[3001];
public static void get_prime(){
    prime[0] = prime[1] = true; // 0과 1은 소수가 아님
    for(int i = 2; i <= Math.sqrt(prime.length); i++){
       if(prime[i]) continue;
       for(int j = i * i; j < prime.length; j += i)
          prime[j] = true;
       }
    }

• 에라토스테네스의 체 사용

• 소수를 체크할 배열 생성

• 0과 1은 소수가 아니기 때문에 prime[0]과 prime[1]을 true로 설정

• 즉, 소수가 아니라면 true

• 2부터 제곱근 이하까지 반복 출력

• 만약 이미 한 번 체크된 배열이면 continue

• i의 배수라면 소수가 아니기 때문에 걸러내기 위해 반복문 사용

• 즉, i의 배수라면 true

public int solution(int[] nums) {
    ArrayList<Integer> sum_a = new ArrayList<>();
    int sum = 0;
    for(int i = 0; i < nums.length; i++){
       if(i+2 >= nums.length) break;
       for(int j = i+1; j < nums.length; j++){
          for(int k = j + 1; k < nums.length; k++){
              sum = nums[i] + nums[j] + nums[k];
              sum_a.add(sum);
          }
       }
    }

• 합을 저장할 List sum_a를 선언

• 세 수의 합을 저장할 변수 sum을 0으로 초기화

• 배열의 합을 구하기 위해 반복문(for문) 사용

• 세 수의 합을 저장한 변수 sum을 sum_a 리스트에 추가

int answer = 0;
get_prime();
for(Integer num : sum_a){
    if(!prime[num]) answer++;
    }
     return answer;
}

전체 코드

import java.util.ArrayList;
    class Solution {
        public static boolean[] prime = new boolean[3001];
        public static void get_prime(){
            prime[0] = prime[1] = true;
            for(int i = 2; i <= Math.sqrt(prime.length); i++){
                if(prime[i]) continue;
                for(int j = i * i; j < prime.length; j += i)
                    prime[j] = true;
            }
        }
        public int solution(int[] nums) {
            ArrayList<Integer> sum_a = new ArrayList<>();
            int sum = 0;
            for(int i = 0; i < nums.length; i++){
                if(i+2 >= nums.length) break;
                for(int j = i+1; j < nums.length; j++){
                    for(int k = j + 1; k < nums.length; k++){
                        sum = nums[i] + nums[j] + nums[k];
                        sum_a.add(sum);
                    }
                }
            }
            int answer = 0;
            get_prime();
            for(Integer num : sum_a){
                if(!prime[num]) answer++;
            }
            return answer;
        }
    }