8회차 - 소수세기

입력 형식

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

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

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

 

출력 형식

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

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

입/출력 예시

 

:

공백

 

:

줄바꿈

 

:

탭

예시 1

입력

 

3
210
50100
1001000

출력

 

Case#1:
4
Case#2:
10
Case#3:
143

 

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);
	public static final int MAX_VALUE = 1000000;
	public static final Sieve sieve = new Sieve(MAX_VALUE);

	public static ArrayList<Integer> getAllPrimeNumbers(int from, int to)
	{
		ArrayList<Integer> primes = new ArrayList<>();

		for(int num = from; num <= to; num += 1)
		{
			if(sieve.isPrimeNumber(num) == true)
			{
				primes.add(num);
			}
		}

		return primes;
	}

	public static void testCase(int caseIndex) {
		int L = scanner.nextInt();
		int R = scanner.nextInt();

		ArrayList<Integer> allPrimeNumbers = getAllPrimeNumbers(L, R);

		System.out.printf("Case #%d:\n", caseIndex);
		System.out.println(allPrimeNumbers.size());
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}

}


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

	/**
	 *
	 * @param num
	 * @return 'num'이 소수라면 true, 그렇지 않으면 false
	 */
	public boolean isPrimeNumber(int num)
	{
		return this.isPrime[num];
	}

	/**
	 * isPrime 배열의 값을 채우는 함수
	 */
	private void fillSieve()
	{
		// 전체 배열을 true 로 선언한다.
		Arrays.fill(isPrime, true);	
	  isPrime[1] = false;
		// 반복문으로 모든 자연수를 오름차순으로 조회수를 한다.
		for( int num =2; num <= maximumValue; num++ ){
			
			// 만약 소수가 아니라면 skip 하고 
			if(isPrime[num] == false){
				// 이미 앞에서 어떤 소인수가 이 수를 배수로써 삭제했다.
				continue;
			}
			
			// 소수라면 배수는 false 로 체크한다.
			for(int mul = num * num; mul <= maximumValue; mul += num){
				isPrime[mul] = false;
			}
		}
	}
}