[TIL] 소수 찾기 알고리즘

문제

해결 방법

💡 소수란, 1과 자기 자신으로만 나눠지는 수(0, 1은 제외)

1. 입력 받은 N+1의 크기만큼의 배열을 선언한다.

🤔
배열의 크기를 N이 아닌 N+1만큼 하는 이유. 배열의 인덱스는 0부터 시작하므로 인덱스의 수와, 실제 소수인지 판별할 수를 일치시키기 위해 +1를 해준다.

2. 1은 소수가 아니므로 2부터 배열의 길이만큼 순회하며 소수인지 판별한다.
3. 해당 숫자의 인덱스를 가진 배열의 값이 0이라면 해당 수가 소수이므로 소수 카운팅을 한다.
4. 해당 숫자의 배수들은 소수일 수 없으므로 배수들의 인덱스를 가진 배열의 값을 1로 변경한다.

class Main2 {
    public int solution(int n) {

        int result = 0;
        int[] arr = new int[n+1];
        for(int i = 2; i<arr.length; i++) {
            if(arr[i] == 0){
                result++;
                for(int j = i; j < arr.length; j= j+i) {
                    arr[j] = 1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        Main2 T = new Main2();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int answer = T.solution(n);

        System.out.println(answer);

    }