에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라스토테네스가 발견한 소수를 찾는 알고리즘이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

구현 순서

1. 자연수 N이 주어지면 자연수 N보다 1만큼 더 큰 일차원 배열을 생성한다.(기본값 0으로 초기화됨)

2. 2번 인덱스부터 차례대로 탐색하며 0을 만나면 0을 1로 바꾸고 해당 인덱스의 배수 인덱스의 값들을 모두 1로 바꾼다.(0을 만났을 때의 인덱스 값이 바로 소수이다.)

3. 이런식으로 N번째 인덱스까지 탐색하면 모든 소수 탐색 완료.

코드로 구현하면 (Java)

import java.util.*;

public class Main {
    static int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
        //2부터 탐색 시작
        for (int i = 2; i <= n; i++) {
        //0을 만나면 소수 갯수를 1개 추가하고 i의 배수 인덱스의 값들을 1로 바꾼다.
            if (arr[i] == 0) {
                answer++;
                for (int j = i; j <= n; j += i) {
                    arr[j] = 1;
                }
            }
        }

        return answer;
    }
}