Algorithm | 소수를 구할때는 에라토스테네스의 체 !!

에라토스테네스의 체

소수를 구할 떄 사용하는 알고리즘 중에 하나이다.
간단한 설명을 하면 전체 n 개라고 가정을 하자
n 개중에 소수를 구하고 싶을 때에는
n 개 만큼 배열을 만든다. 후에 그 배열에서 0 , 1 은 소수가 아님으로 제외
후에 2 부터 제곱 근 만큼 나누었을떄 0 이라면 true 로 반환 해준다.

Java Code

백준에서 1929 번 문제이다. a와b 두사이의 소수를 구하는 문제인데
에라토스테네의 체을 이용하였다.
여기서 키 포인트는 Math.sqrt 제곱근 함수를 이용하기 위함이다.
boolean 배열에서 end size + 1 로 만들어주고
true 가 아니면 소수 false 이면 소수이다.

소수란 2~8 사이로 나누었을때 0 이 아닌 수 이다

    public void solution(int a, int b) {

        boolean[] booleans = new boolean[b + 1];

        booleans[0] = booleans[1] = true;

        for (int i = 0; i < booleans.length; i++) {
            boolean booleanData = booleans[i];
            if (!booleanData) {
                for (int j = 2; j < Math.sqrt(i); j++) {
                    if (i % j == 0) booleans[i] = true;
                }
            }
        }

        for (int i = a ; i <= b ; i++){
            if (!booleans[i]){
                System.out.println(i);
            }
        }

        return;
    }