[Java] 소수 세기

1. 문제 설명

주어진 범위에 존재하는 소수의 수를 출력하는 프로그램을 작성

입력 형식

첫 줄에는 테스트케이스의 수 T가 주어진다. T는 1이상 10이하의 자연수이다.

각 테스트케이스의 입력으로는 한 줄에 1이상 100만이하의 두 자연수 L과 R이 공백으로 구분되어 주어진다.

L R 순서로 주어지며 L은 항상 R이하의 값이다.

출력 형식

각 테스트케이스에 대하여 두 줄씩 정답을 출력한다.

테스트케이스의 첫 줄에는 테스트케이스의 번호를 Case #%d: 형식으로 출력한다.
두 번째 줄에는 L이상 R이하의 소수의 갯수를 공백없이 출력한다.

2. 알고리즘 접근

L ~ R까지 순회하며 소수판별을 하는 알고리즘이다.
소수의 판별 << 클릭
위 방식의 소수 판별은 O($\sqrt n$)의 시간복잡도를 가지나
위 방식을 그대로 적용한다면 worstCase L~R을 순회할 때 100만번 수행하기에
O(n$\sqrt n$)의 시간복잡도를 가져 시간 초과하게 된다

에라토스테네스의 채

주어진 범위 내의 모든 자연수에 대한 소수 여부를 계산하는 알고리즘

• 한번 수행하면 주어진 범위의 모든 자연수에 대한 결과를 계산하고 배열에 저장
• O(N)의 공간 사용
• O(N loglogN)의 시간을 사용
• 다양한 변형과 활용 가능

사용법

1. isPrime[] 배열 선언
	isPrime[p] // 자연수 p의 소수여부 저장 (default : true)

2. isPrime[1] = false

3. [2, n] 사이에 소수 판별 과정 수행
	1. 해당 숫자가 이미 소수가 아니라고 저장되어 있다면 건너뛴다
    2. 그렇지 않다면, 해당 숫자는 소수이다
    3. 이 숫자의 모든 배수를 소수가 아니라고 체크

무조건 에라토스테네스의 채가 좋은것이 아님 -> O(N)의 공간을 사용하기 때문
즉 N의 크기가 작고 빠르고 여러번 재활용할 때 이 알고리즘을 사용하고
N의 크기가 크고 단발성으로 사용할 때 반복문을 이용한 소수판별을 하자

3. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

// 소수 세기 알고리즘
public class Q4F {
    static final Scanner sc = new Scanner(System.in);
    static final Sieve sieve = new Sieve(1000000);

    private static ArrayList<Integer> getAllPrimeNumbers(int l, int r) {
        // l ~ r의 소수를 구하자 ex) 2, 5 -> 2, 3, 5

        ArrayList<Integer> primes = new ArrayList<>();

        for(int num = l; num <= r; num++){
            if(sieve.isPrimeNumber(num) == true){
                primes.add(num);
            }
        }
        return primes;
    }

    private static void testCase(int caseIndex) {
        int l = sc.nextInt(); // 자연수 L (L은 항상 R이하)
        int r = sc.nextInt(); // 자연수 R

        ArrayList<Integer> allPrimeNumbers = getAllPrimeNumbers(l, r);

        System.out.printf("Case #%d:", caseIndex);
        System.out.println(allPrimeNumbers.size()); // arrayList의 크기를 가져와 개수 파악

    }

    public static void main(String[] args) {
        // 주어진 범위에 존재하는 소수의 수를 출력하는 프로그램 작성
        int caseSize = sc.nextInt();
        for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
            testCase(caseIndex);
        }
    }
}

class Sieve { // 소인수분해를 빠르게
    final int maximumValue; // 에라토스테네스의 체에서 다룰 가장 큰 범위의 값
    final boolean[] isPrime; // 각 숫자별 소수 여부
    Sieve(int maximumValue){
        this.maximumValue = maximumValue;
        this.isPrime = new boolean[maximumValue+1];
        this.fillSieve();
    }
    public boolean isPrimeNumber(int num){
        return this.isPrime[num];
    }

    // isPrime 배열값 채우는 함수
    private void fillSieve() {
        Arrays.fill(isPrime, true); // 모두 true로 초기화

        // 반복문으로 모든 자연수를 오름차순으로 조회하고
        // 만약 소수가 아니라면 스킵하고 소수라면 배수를 false처리
        for(int i = 2; i <= maximumValue; i++){
            if (isPrime[i] == false){
                // 이미 앞에서 어떤 소인수가 이 수를 배수로서 삭제했다
                continue;
            }
            // num은 소수다
            for(long mul = (long)i * i; mul <= maximumValue; mul+=i){ // 이미 2부터 i - 1까지의 배수는 이미 삭제했으니 스킵
                isPrime[(int)mul] = false;
            }
        }
    }

}