[프로그래머스] 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

import java.util.Arrays;


class Solution {
    public int solution(int n) {
        //n+1개의 배열을 만들기
        boolean[] arr = new boolean[n+1];
        //초기화 : 모든 값을 true로 입력
        Arrays.fill(arr, true);
        //0과 1은 소수가 아니니 제외
        arr[0] = arr[1] = false;

        //2부터 시작
        //아래 for문에서 배수에 해당하는 수는 모두 지울 것이므로 횟수 제한
        for (int i = 2; i*i <= n; i++){
            //이미 지워진 수는 제외
            if(arr[i] == true) {
                //본인 빼고 그 배수 모두 제외
                for(int j = i*i; j <=n; j+=i) {
                    arr[j] = false;
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < n+1; i++) {
            if(arr[i] == true) answer++;
        }
        return answer;
    }

    //출력을 위한 부분
    public static void main(String[] args) {
        Solution method = new Solution();
        System.out.println(method.solution(15));
    }
}

소수를 구하는 문제이다.

효율성에서 계속 통과하지 못해서 찾아보니 '에라토스테네스의 체'를 이용해야하는 문제였다.

소수가 되는 수의 배수를 지우면 남는 건 소수가 된다는 알고리즘이다.

2부터 자기 자신을 제외한 배수가 되는 것을 모두 지우면 된다.

(참고: https://firework-ham.tistory.com/8)

 

JAVA로 구현할 때는 boolean을 이용해주면 된다.

배열을 채울 때는 Arrays.fill(배열 이름, 입력하려는 수)로 한번에 초기화할 수 있다.

 

알고리즘 지식이 필요한 문제라 빨리 답안을 보고 이해하는 게 더 좋았을 것 같다.