040 : 제곱이 아닌 수 찾기

(Briefing)
문제	단 하나의 맥락	입출력과 되어야 하는 그림
어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 이 수는 제곱이 아닌 수이다 여기서 제곱수는 정수의 제곱이다 min과 Max값이 주어지고, 이 사이에서 제곱이 아닌 수가 몇개나 있는지 출력하시오(같지 않은)

1 <= min <= 1,000,000,000,000

min <= max <= min + 1,000,000 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        long Min = sc.nextLong();
        long Max = sc.nextLong();

        // Preprocessing
        boolean[] Check = new boolean[(int) (Max - Min + 1)];

        // Operating Sieve(1/2)
        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;
            }
        }

        // Operating Counter(2/2)
        int count = 0;
        for (int i = 0; i <= Max - Min; i++) {
            if (!Check[i]) {
                count++;
            }
        }

        // Output Extracting Cable
        System.out.println(count);
    }
}

(경향성과 모듈)

- 2^2부터  i^2(<=Max) 까지 나누어 떨어지면 제곱수

- 또한 각 i^2에 2부터 j까지(j<=Max) 배수로 나누어 떨어져도 제곱수

- 제곱수를 구한 뒤, 제곱수가 아닌 것을 출력한다

 

(절차적 부분 / 미시 보정)

- index