[Java] BOJ 4134: 에라토스테네스의 체

소수 검증

static boolean isPrimeNumber(int n) {
    if (n < 2) {
        return false;
    }
    for (int divisor = 2; divisor <= Math.sqrt(n); divisor++) {
        if (n % divisor == 0) {
            return false;
        }
    } return true;
}

▶ 특정 숫자가 소수인지를 판단할 때, 우리는 해당 숫자의 제곱근까지만 약수 여부를 검증하면 된다. 그런데 만약, 범위 내의 소수를 모두 알고 싶다면 어떻게 해야 할까?

---

범위 내 소수 검증

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int start = sc.nextInt();
    int end = sc.nextInt();

    for (int i = start; i <= end; i++) {
        if (isPrimeNumber(i)) {
            System.out.println(i);
        }
    }
}

// 소수 검증 메서드
static boolean isPrimeNumber(int n) {
    if (n < 2) {
        return false;
    }
    for (int divisor = 2; divisor <= Math.sqrt(n); divisor++) {
        if (n % divisor == 0) {
            return false;
        }
    } return true;
}

▶ 앞서 제시한 메서드를 사용하면, 당연히 반복문을 통해 범위 내 소수를 나열할 수 있다. 하지만 입력된 범위가 커지면 커질수록 더 많은 연산이 필요하기 때문에 성능 측면에서 비효율적이다. 에라토스테네스의 체를 사용하여 성능을 개선해 보자.

---

에라토스테네스의 체

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int start= sc.nextInt();
    int end = sc.nextInt();
    int[] nums = new int[end + 1];

    for (int i = 2; i <= end; i++) {
        nums[i] = i;
    }

    // 에라토스테네스의 체
    for (int i = 2; i <= Math.sqrt(end); i++) {
        if (nums[i] == 0) {
            continue;
        }
        for (int j = i * i; j <= end; j += i) {
            nums[j] = 0;
        }
    }

    for (int i = start; i <= end; i++) {
        if (nums[i] != 0) {
            System.out.println(nums[i]);
        }
    }
}

---

[코드 분석]

int[] nums = new int[end + 1]

▶ 0번 인덱스을 고려해 배열의 크기를 1 늘려 선언한다.

for (int i = 2; i <= end; i++) {
    nums[i] = i;
}

▶ 2번 인덱스부터 값을 넣어줌으로써, 1은 자연스럽게 소수에서 제외한다.

---

for (int i = 2; i <= Math.sqrt(end); i++) {...}

▶ 검증에 필요한 수는 마지막 숫자의 제곱근까지다.

if (nums[i] == 0) {
    continue;
}

▶ 이미 지워진 숫자는 건너뛴다.

for (int j = i * i; j <= end; j += i) {...}

▶ j = i * i로 하는 이유는 i보다 작은 배수들은 이미 제거된 상태이기 때문이다.

---

for (int i = start; i <= end; i++) {
    if (nums[i] != 0) {
        System.out.println(nums[i]);
    }
}

▶ 입력된 범위 내 소수를 출력한다.