[Java] 1456번. 거의 소수 (#소수 판정)

1. 문항출처 : https://www.acmicpc.net/problem/1456

2. 문제해석

숫자범위 A에서 B가 주어지고,
어떤 소수의 N제곱이 주어진 숫자범위 [A,B]에 속하는 경우의 수를 찾는 것이다.
이 문제는 까다롭게 짚고 넘어가야할 부분이 2가지가 있는데,
첫번째는 소수를 찾는 로직이고,
두번째는 소수의 N제곱이 [A,B]에 속하는지('거의 소수'가 범위에 속하는지) 판단하는 로직이다.

1) 소수 찾는 로직

소수를 찾을 때, 모든 숫자마다 이 수가 소수인지를 판별하게 되면
중복이 많아서 시간초과가 나게되므로 최대범위인 B보다 작은 범위에서만
소수를 '에라토스테네스의 체'를 이용하여 중복없이 소수를 찾아야한다.

2) '거의 소수'를 찾는 로직

A,B의 최대입력값을 10^14으로 int형 범위(10^9)를 넘어가게 되고
long형 범위는 10^18이지만
소수가 충분히 크게 된다면(가령 10^10 크기),
제곱을 하는 것만으로도 long 형 범위를 넘어가게 되므로 오류가 나게 된다.
따라서 범위에 속하는 판단을 할 때,
A,B 크기를 작게하여 판단하는 트릭이 필요하다.

3. 해결코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long start = Long.parseLong(st.nextToken());
        long end = Long.parseLong(st.nextToken());
        
        // 소수를 판별할 범위 설정
        boolean[] isPrime = new boolean[(int) Math.sqrt(end) + 1];
        for (int i = 2; i < isPrime.length; i++) isPrime[i] = true;
		
        // '에라토스테네스의 체'를 이용한 소수찾기
        for (int i = 2; i < isPrime.length; i++) {
        	// 해당 i가 소수가 아니면 건너뛰기
            if (!isPrime[i]) continue;
            // i가 소수이면 i의 배수는 모두 소수가 아님을 표기
            for (int j = i * 2; j < isPrime.length; j += i) {
                isPrime[j] = false;
            }
        }
        
        // 주어진 범위 [A,B]에 해당하는 '거의 소수'의 개수 찾기
        int answer = 0;
        // 찾아낸 소수에 대해서 N제곱이 범위에 해당하는지 찾기 시작
        for (int i = 2; i < isPrime.length; i++) {
        	// i가 소수인 경우에만
            if (isPrime[i]) {
                long temp = i;
                // 자료형의 범위를 넘어가지 않게 양변을 i로 나눈값으로 범위에 속하는지 판단
                while (temp <= (double) end / i) {
                    if (temp >= (double) start / i) {
                        answer++;
                    }
                    temp *= i;
                }
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}