[알고리즘] 1016번

오늘 풀어볼 문제는 백준 1016번 문제 "제곱 ㄴㄴ 수" 이다.

이 문제는 골드1 문제이고 정수론 문제이다.

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 
제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

📌첫 번째 도전📌
min과 max를 입력받아 범위 내에서 문제에서 요구하는 제곱수로 나누어 떨어지는 값을 true로 하고 마지막에 false의 갯수를 세어 출력하는 방식으로 풀었다.

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

        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());

        boolean[] check = new boolean[(int) (max - min + 1)];

        for(long i=2; i*i<=max; i++) {
            long pow = i * i;
            long start_index = min / pow;
            if(min % pow != 0) {
                start_index++;
            }
            for(long j = start_index; pow * j <= max; j++) {
                check[(int) ((j*pow) - min)] = true;
            }
        }
        int count = 0;

        for(int i=0; i<=max-min; i++) {
            if(!check[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1016