[백준][Gold1] 제곱ㄴㄴ수 - JAVA

[문제 설명]

www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

문제는 간단하지만 풀다보니 시간효율성을 통과하는 것이 까다로워 가히 Gold 레벨에 있는것이 납득이 가는 문제다. 

문제를 읽고 일반 코드로 풀어보니 시간 초과가 나면서 통과하지 못했다. 

에라토스테네스의 체 원리를 이용하여 된다.

 

[JAVA code]

package com.algorithm.baekjoon.silver5;

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

public class Test05 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        long min = Long.parseLong(strs[0]);
        long max = Long.parseLong(strs[1]);
        solution(min, max);
    }

    public static void solution(long min, long max) {
        boolean[] checkArray = new boolean[1000001];
        Arrays.fill(checkArray, false);

        int end = (int) Math.sqrt(max);
        for (int i = 2; i <= end; i++) {
            long pow = (long) Math.pow(i, 2);
            long count = min / pow == 0 ? pow : (min / pow) * pow;
            for (long j = count; j <= max; j += pow) {
                if (j >= min) {
                    if (checkArray[(int) (j - min)]) {
                        continue;
                    }
                    checkArray[(int) (j - min)] = true;
                }
            }
        }

        long answer = 0;
        for (int i = 0; i < checkArray.length; i++) {
            answer += checkArray[i] == true ? 1 : 0;
        }

        System.out.println(max - min + 1 - answer);
    }
}