백준 1016번 자바 ☆

1. 문제

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

1016번: 제곱 ㄴㄴ 수

 

2. 접근 방식

어떤수 X는 1보다 큰 제곱수로 나눠지지 않는다 => 소수의 제곱으로도 안나눠지면 제곱 ㄴㄴ수다.

이유는 아래에 다시 설명 하겠다.

 

먼저 에라토스테네스의 체로 소수를 구해준다.

해당 인덱스의 소수를 제곱해주고 제곱수를 min과 나눠준다.

이때 수가 나누어 떨어진다면 그대로 다음 반복문으로 이동하고 나누어 떨어지지 않는다면 divVal의 값을 +1해준다.

 

예를 들어 min이 10이고 첫번째 소수인 2부터 시작할 때

10(min)/4(square) = 2.5 -> 2(divVal)

2(divVal) * 4(square) = 8 < 10(min)

다시 말해서 (제곱수 * 몫)은 곧 나누어떨어지는 수(제곱ㄴㄴ수가 아니다.)이며 해당 값을 정답에서 제외 시킨다.

그러므로 나머지가 있을 경우 +1을 해줘서 min보다 크고 제곱수로 나눠지는 수를 찾는다.

나누어 떨어질 경우 해당 수 부터 차례대로 몫을 증가시켜 그 다음 수들도 제외 시킨다.

 

그렇다면 왜 모든 수의 제곱수로 나눌 필요없이 소수로만 나누어도 문제 해결이 될까?

그 이유는 소수를 구할 때를 생각하면 간단하다.

 에라토스테네스의 체를 이용하면 

 

예를 들어 108이라는 수는 6의 제곱인 36으로 나누어진다. 

하지만 순차적으로 구할 경우 2의 제곱인 4의 배수에서 먼저 제외된다.

즉, 소수외 다른 수들의 제곱은 결국 약수가 소수의 제곱수로 이루어지기 때문에 소수의 제곱수만으로 정답을 구할 수 있는 것이다.

 

 

3. 구현

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

public class Main1016 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long min = Long.parseLong(st.nextToken());
		long max = Long.parseLong(st.nextToken());
		int[] arr = new int[1000001];
		for (int i=2; i<arr.length; i++) {
			arr[i] = i;
		}
		for (int i=2; i<Math.sqrt(arr.length); i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j=i+i; j<arr.length; j+=i) {
				arr[j] = 0;
			}
		}
		boolean[] answer = new boolean[(int)(max-min+1)];
		for (long i=2; i<arr.length; i++) {
			if (i*i > max) {
				break;
			}
			if (arr[(int)i] == 0) {
				continue;
			}
			long square = i*i;
			long divVal = min/square;
			if (min%square != 0) {
				divVal++;
			}
			for (long j=divVal; j*square<=max; j++) {
				answer[(int)((j*square)-min)] = true;
			}
		}
		
		int cnt = 0;
		for (int i=0; i<answer.length; i++) {
			if (!answer[i]) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

4. 정리

역시나 수학적인 센스가 필요한 문제는 어렵다.