1016

이건 그냥 문제가 어려웠다..... 한참 생각해도 모르겠어서 풀이법 참고

접근법

min 범위를 보면 전체 범위를 배열로 접근하는 건 불가능하다.
주목해야할 건 min이랑 max 사이 값들인데 어차피 문제에서 구해야하는 수는 min~max 사이 값들이니까 이만큼만 배열로 잡아서 에라토스테네스의 체를 사용한다

2부터 max의 제곱근까지 탐색하면서 i의 제곱수를 구한다.
제곱수는 (제곱수/min 의 몫) * 제곱수

코드 자체는 짧은데 풀이 생각해내는게 어려웠던 문제....

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


public class Main {
    static boolean[] check;
    static long min, max;
    static int diff;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        min = Long.parseLong(st.nextToken());
        max = Long.parseLong(st.nextToken());
        diff = (int) (max-min+1);
        check = new boolean[diff];
        getPrime();
        System.out.println(diff);
    }

    static void getPrime(){
        for (long i = 2; i <= (int)Math.sqrt(max); i++){
            long pow = i*i;
            long tmp = min / pow;
            if (min % pow != 0){
                tmp++;
            }

            for (long j = tmp; j * pow <= max; j++){
                int idx = (int)(j*pow - min);
                if (!check[idx]){
                    check[idx] = true;
                    diff--;
                }
            }
        }
    }
}