[백준] 1456번 - 거의 소수 (Silver 1)

문제 링크

백준 1456번 - 거의 소수 (Silver 1)

문제 설명

거의 소수란 한 소수의 거듭제곱 꼴로 표현되지만, 소수는 아닌 수를 뜻한다.
두 정수 A와 B가 주어졌을 때 A 이상 B 이하인 거의 소수가 몇 개인지 출력하시오.
단, $1 \leq A \leq B \leq 10^{14}$이다.

정답 코드 및 설명

$10^{14}$ 이하인 거의 소수는 $\sqrt{10^{14}} = 10^7$ 이하인 소수의 거듭제곱 꼴이다.
$10^{7}$ 이하의 소수를 모두 저장하고, 각 소수에 대해 A 이상 B 이하인 거듭제곱(소수 자신은 제외)이 총 몇 개인지를 구하면 된다.

소수를 구하는 과정은 에라토스테네스의 체를 이용하였다. 코드의 11행 ~ 16행에 해당한다.
거의 소수의 갯수를 세는 과정은 코드의 27행 ~ 37행에 해당한다.

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

public class BOJ1456 {
    final int MAX = 10_000_000;
    long a, b;
    boolean[] isNotPrime = new boolean[MAX + 1];

    void setPrime() {
        isNotPrime[0] = isNotPrime[1] = true;
        for(int i = 2; i * i <= MAX; i++) {
            if(isNotPrime[i]) continue;
            for(int j = 2 * i; j <= MAX; j += i)
                isNotPrime[j] = true;
        }
    }

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Long.parseLong(st.nextToken());
        b = Long.parseLong(st.nextToken());
    }

    void solution() throws IOException {
        setPrime();
        input();
        long count = 0;
        for(long j = 2; j <= MAX; j++) {
            if(isNotPrime[(int)j]) continue;
            long curr = j * j;
            while(curr <= b) {
                if(curr >= a) count++;
                if(j > 100_000) break;
                curr *= j;
            }
        }
        System.out.println(count);
    }

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