[백 준 Java] 1016번 문제 : 제곱 ㄴㄴ수

문제 설명

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

 

입력

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

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

제한

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

알고리즘

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

푼 방법

에라토스테네스의 체를 응용해서 접근했다.

에라토스테네스의 체는 여기서 설명해놓았다.

https://coreeny.tistory.com/36

[알고리즘] 에라토스테네스의 체

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        long min = Long.parseLong(tokenizer.nextToken());
        long max = Long.parseLong(tokenizer.nextToken());

        boolean[] isPower = new boolean[(int) (max - min + 1)];
        int count = 0;

        for (long i = 2; i * i <= max; i++) {
            long mini = min / (i * i);
            if (mini * i * i < min) {
                mini++;
            }
            for (long j = mini; i * i * j <= max; j++) {
                isPower[(int)(i * i * j - min)] = true;
            }
        }

        for (boolean e : isPower) {
            if (!e) {
                count++;
            }
        }
        System.out.println(count);
    }
}

링크

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

1016번: 제곱 ㄴㄴ 수