[BOJ_1456] 거의 소수

설명

---

계속 시간 초과가 나길래 prime을 항상 범위의 수를 탐색 할 때 마다 구하고 있었다 처음에는... 상당히 버거운 코드 였고 이를 개선하여 1차적으로 prime 배열을 두고 항상 사용하였고 이후에는 Long 범위가 넘어 갈 때 대처가 잘 안 되어서 while문 내부에서 오버플로가 나길래 num > Long.MAX_VALUE / (i -> 소수 값) 을 넣어서 구할 수 있었다.

 

코드

---

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class BOJ_1456 {
    static Set<Long> set;
    static boolean[] isPrime;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");

        long A = Long.parseLong(tk.nextToken());
        long B = Long.parseLong(tk.nextToken());

        set = new HashSet<>();
        isPrime = new boolean[(int) Math.sqrt(B) + 1];

        getPrime();

        for (long i = 2; i * i <= B; i++) {
            if (isPrime[(int) i]) {
                long num = i * i;
                while (num <= B) {
                    if (num >= A) {
                        set.add(num);
                    }
                    if (num > Long.MAX_VALUE / i) {
                        break;
                    }
                    num *= i;
                }
            }
        }

        System.out.println(set.size());
    }

    private static void getPrime() {
        for (int i = 2; i < isPrime.length; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i < isPrime.length; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}

1456번: 거의 소수