[백준] 1456 거의 소수 java 풀이

1. 문제 설명 📌

문제 링크

2. 구현 방법 🗃️

KEY WORD: 에라토스테네스의 체

문제에서 주어진 영역의 최소값 A, 최대값 B, 임의의 소수 K에 대하여, $A < K^{n} < B$ 가 성립하는 $K^{n}$의 개수를 세라는 문제이다. B의 최대값은 $10^{14}$이다. java의 long 자료형의 최대값이 $10^{18}$이지만, 제곱을 구한다는 면에서 $K^{n}$이 $10^{18}$을 훌쩍 뛰어넘을 가능성이 있다. 따라서 이에 대한 처리를 해줘야 한다.

• 0️⃣ $A < K^{n} < B$인 $K^{n}$을 구하는 문제이다. K의 최대값은 n을 문제에서 주어진 최소값인 2로 설정했을 때 구할 수 있을 것이다. 따라서 가능한 K를 모두 구하기 위해, n을 2라고 치고, 양변을 모두 2의 제곱근으로 나눈다. $√A < K < √B$ 이것이 바로 우리가 구해야 할 K의 영역이다.
• 1️⃣ 1 < K < √B까지의 소수를 구한다. (에라토스테네스의 체), √√B까지의 숫자를 살펴보면 될 것이다.
• 2️⃣ 구해진 소수들을 계속 제곱하며, B보다 작을 때까지 가능한 수의 개수를 센다. 이때 우리는 Long이 아닌 Double 자료형을 사용한다. double 자료형은 지수표기법으로 값을 나타내기 때문에 정밀도는 조금 떨어질 수 있으나, Long보다 큰 값도 overflow 없이 표현 가능하다. 이번 문제가 정확한 값을 구하는 것이 아닌 대소 비교임으로 충분히 사용 가능하다.
  (double 값 반환하는 Math.pow()이용)

(1) 시간복잡도 분석 🕓

소수 판별을 해야하는 최대값: √B, 누적해 제곱한 값이 B보다 작은지 확인할 값: i라고 할 때,

• 소수 판별: $O(√B \log(\log √B))$
• $K^{n}$ 세기: $O(√B \log_i B)$

3. 코드 소개 🔎

(1) SUDO CODE

1. 입력 받기;
2. √B 내의 소수값 찾기;
3. √B 내의 소수에 대하여 그것을 누적해 제곱한 값 중 B를 안 벗어나는 값의 개수 세기

(2) JAVA CODE

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


public class Main {
    static long  A, B;
    static long [] nums;        // 0 = true, 1 = false
    public static void main(String[] args) 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());
        nums = new long [(int)Math.sqrt(B) + 1];
        prime_shifter();
        System.out.println(counting_almost_prime());
    }

    public static void prime_shifter(){
        nums[0] = 1;
        nums[1] = 1;
        for (int i = 2; i <= Math.sqrt(Math.sqrt(B)); i++) {
            if(nums[i] == 0){
                for (int j = i*i; j <= Math.sqrt(B); j+=i) {
                    nums[j] = 1;
                }
            }
        }
    }

    public static int counting_almost_prime(){
        int cnt = 0;
        for (long i = 2; i <= Math.sqrt(B); i++) {
            if(nums[(int)i] == 0){
                double j = i*i;
                double acc = 2;
                while(j <= B){
                    if(j >= A) cnt++;
                    j = Math.pow(i, ++acc);
                }
            }
        }
        return cnt;
    }
}

4. 배운 것들 🎯

아직 이항 정리를 통해 푸는 방법에 대한 감을 못 잡겠다.