[코딩테스트] 백준 1456 자바

백준 1456

백준 1456 문제

해당 문제는 최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결할 수 있다.

입력에서 주어진 범위의 최댓값 1014의 제곱근인 107까지 소수를 탐색해야 한다.

에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구한다. 그 이후에는 주어진 소수들이 A ~ B 범위 안에 존재하는지 판별해 유효한 소수의 개수를 세면 이 문제를 해결할 수 있다.

import java.util.*;

public class Boj1456 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(); // 시작 수
        long b = sc.nextLong(); // 종료 수
        long[] arr = new long[1000001]; // 소수 배열
        int count = 0; // 정답값

        for (int i = 2; i < arr.length; i++) { // 10의 14제곱의 제곱근인 1000000까지 반복
            arr[i] = i; // 각각의 인덱스값으로 초기화
        }

        for (int i = 2; i <= Math.sqrt(arr.length); i++) { // 1000000의 제곱근까지만 수행
            if (arr[i] == 0) { // 소수가 아니면 넘어감
                continue;
            }

            for (int j = i + i; j < arr.length; j += i) { // 소수의 배숫값을 1000000까지 탐색
                arr[j] = 0; // 이 수가 소수가 아니라는 것을 표시 (배수 지우기)
            }
        }

        for (int i = 2; i < arr.length; i++) { // 1000000까지 반복
            if (arr[i] != 0) { // 소수 배열에서 소수인 값일 때
                long temp = arr[i]; // 현재 소수를 temp에 저장

                // 현재 소수의 제곱근이 b보다 작을 때를 기준으로 하지만 곱셈이 long의 범위를 넘어갈 수 있어 이항 정리로 처리
                while ((double) arr[i] <= (double) b / (double) temp) {
                    if ((double) arr[i] >= (double) a / (double) temp) {
                        count++; // 정답값 증가
                    }

                    temp *= arr[i]; // temp에 현재 소수 곱하기
                }
            }
        }

        System.out.println(count); // 정답 출력
    }
}

풀이

1. 시작 수를 a에 입력 받아 저장한다.
2. 종료 수를 b에 입력 받아 저장한다.
3. 소수 배열 arr의 크기를 최댓값의 제곱근(1000001)로 선언한다.
4. 정답값 count를 0으로 초기화한다.
5. 소수 배열 크기만큼 반복하며 소수 배열의 값을 각각의 인덱스값으로 초기화한다.
6. 소수 배열 크기의 제곱근 Math.sqrt(arr.length) 만큼 반복하면서 arr[i] == 0이면 즉, 소수가 아니면 넘어간다.
   6-1. 소수이면, 소수 배열의 크기까지 탐색하면서 소수의 배수를 0으로 소수가 아니라는 것을 표시한다. (배수 지우기)
7. 소수 배열의 크기만큼 반복하면서 소수인 수는 temp 변수에 저장한다.
   7-1. 소수의 제곱이 long 범위를 넘어갈 수 있기 때문에 이항 정리로 처리하면서 소수가 b / temp보다 작고 a / temp보다 크면 정답값을 증가시킨다.
   7-2. temp에 현재 소수를 곱해주면서 반복한다.
8. 모든 반복이 끝나면 정답값 count를 출력한다.