[Java] 백준 1016 제곱ㄴㄴ수 - 소수 구하기(4)

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

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

출력

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

---

제출

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long Min = sc.nextLong();
		long Max = sc.nextLong();
		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);
	}
}

예제

1 10

 

15 15

1 1000

결과

백준 1016 제곱ㄴㄴ수

 

1016번: 제곱 ㄴㄴ 수