[BOJ][Java] 1456번 거의 소수

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1456

 

이 문제는 소수를 적절히 구하고 해당 소수를 N 제곱하면서 A와 B 사이의 값의 개수를 찾는 문제이다.

에라토스테네스의 체를 이용하여 소수를 구한다.

이때 최댓값은 문제의 조건에 따라 10^14의 제곱근인 10^7 까지만 구하면 된다.

 

소수를 구했으면 소수를 하나씩 순회하면서

제곱 중 문제 조건에 맞는 소수가 있을 때마다 answer 값을 하나씩 늘려준다.

이때 제곱을 구하면서 long 타입의 최댓값보다 값이 커질 수 있기 때문에 

조건문을 활용하여 오버플로우를 방지해야 한다.

 

package boj;

import java.util.*;
import java.io.*;

public class BOJ1456 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] arr = new int[10000001];

        for(int i = 2; i < arr.length; i++){
            arr[i] = i;
        }

        for(int i = 2; i < arr.length; i++){
            if(arr[i] == 0) continue;
            for(int j = i + i; j < arr.length; j = j + i){
                arr[j] = 0;
            }
        }

        int answer = 0;
        for(int i = 2; i <= Math.sqrt(B) ; i++){
            if(arr[i] != 0){
                long temp =  (long)i * i;
                while(temp <= B){
                    if(temp >= A){
                        answer++;
                    }
                    if (temp > B / i) break;
                    temp *= i;
                }
            }
        }


        System.out.println(answer);
    }
}