[BOJ/JAVA] 1016번: 제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

문제

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

입력

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

출력

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

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력 1 

1 10

예제 출력 1 

7

예제 입력 2 

15 15

예제 출력 2 

1

예제 입력 3 

1 1000

예제 출력 3 

608

이 문제에서 가장 중요한 것은 제한이다.

 

min의 최댓값은 1,000,000,000,000 까지이다.

max의 최댓값은 min + 1,000,000 까지이다.

int 형으로는 대략 2,100,000,000 까지이다.

 

int 형으로는 1,000,000,000,000 까지 계산할 수 없다는 것을 알았다.

 

그래서 계산할 때는 long을 이용하여 1,000,001,000,000 까지 연산이 가능하도록 조정하였다.

 

그 다음 제곱 ㄴㄴ수를 어떻게 구하는가를 생각했다.

그래서 1보다 큰 제곱수를 나열 해 보았다.

4 9 16 25 36 49 64 81 ...

만약 16으로 나누어 떨어진다면, 4로도 나누어 떨이지게 되어있다.

제곱하기 전의 값인 2와 4는 서로소가 아니다. -> 소수의 제곱수만 구하자

라는 결론을 내렸다.

 

사실 1부터 1,000,000,000,000 까지 모든 소수를 구한다는 것은 시간상 너무 오래걸린다.

 

그래서 [min, max] 에서 제곱수인지 아닌지만 판단하기로 했다.

만약 i 가 소수라고 하자. 소수의 제곱수 즉 i * i 로 나누었을 때 나머지가 0일 때 제곱 ㄴㄴ 수가 된다.

이를 판별하기 위해 [min, max]에서 제곱 ㄴㄴ 수를 추출해야 하는데,

2가지 경우의 수로 나뉜다. 

1. min이 i * i 로 나누었을 때 나머지가 0인 경우

2. min이 i * i 로 나누었을 때 나머지가 0이 아닌 경우

 

1. 의 경우는 min 부터 i * i 를 계속 더해가면서 제곱 ㅇㅇ 수를 추출했다.

 

2. 의 경우는 min 보다 크고, i * i 로 나누었을 때 나머지가 0인 가장 작은 수를 찾아야한다.

따라서 min을 i * i로 나누었을 때의 몫보다 1만큼 큰 i * i 의 배수를 취하기로 했다.

따라서 수식은 다음과 같다.

(i * i) * ((min / (i * i)) + 1)

위의 수 부터 i * i 를 계속 더해가면서 제곱 ㅇㅇ 수를 추출한다.

 

하지만 아래 코드의 배열에서 보면 check [(int) (j - min)] 라고 되어있다.

배열을 무작정 min크기를 만들 수 없어서, [min-min, max-min] 까지 크기로 결정하였다.

따라서 해당하는 값에 min을 빼주면 압축된 인덱스에 체크를 확인할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class java_1016 {
    public static boolean[] isPrime;
    public static boolean[] check;

    // N까지 소수 체크
    public static void check_prime(long min, long max) {
        isPrime = new boolean[(int) Math.sqrt(max) + 1];
        check = new boolean[(int) (max - min + 1)];

        Arrays.fill(isPrime, true);
        Arrays.fill(check, true);

        for (long i = 2; i <= (int) Math.sqrt(max); i++) {
            if (!isPrime[(int) i]) {
                continue;
            }

            for (long j = i * i; j < Math.sqrt(max); j += i * i) {
                isPrime[(int) j] = false;
            }

            // min이 i의 제곱수로 나누어 떨어지면.. min 그대로 배수를 제곱수 처리
            // min이 i의 제곱수로 나누어 떨어지지 않으면...min보다 큰 제곱수부터 제곱수 처리
            long squared = i * i;
            long j = min % squared == 0 ? min : squared * ((min / squared) + 1);
            for (; j <= max; j += squared) {
                check[(int) (j - min)] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        // 1보다 큰 제곱수
        // 4 9 16 25 36 49 64 81 ...

        // 16으로 나누어 떨어진다면 4로도 나누어 떨어짐
        // 4로도 나누어 떨어진다면 16으로도 나누어 떨어짐
        // -> 소수의 제곱수만 구하자

        // 소수 제곱 -> 체로 거르자

        // 제곱 ㄴㄴ 수
        // 1 2 3 5 6 7 8 10

        // 1. 소수 구하기
        // 어디까지의 소수를 구할 것인가?
        // Math.sqrt(max) 까지의 소수를 구하자
        // 2. 체로 거르기

        check_prime(min, max);
        // for (int i = 0; i < isPrime.length; i++) {
        // System.out.println("i : " + i + " : [ " + isPrime[i] + " ]");
        // }

        long result = 0;

        for (long i = min; i <= max; i++) {
            if (check[(int) (i - min)]) {
                result++;
            }
        }

        System.out.println(result);

        br.close();
        bw.close();
    }
}