[백준] 제곱 ㄴㄴ 수 1016 - JAVA

문제

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

1016번: 제곱 ㄴㄴ 수

풀이

에라토스테네스의 체를 활용하여 푸는 문제다.

문제에서 제곱수의 배수로 나누어 떨어지지 않을 경우 제곱 ㄴㄴ 수라고 하였다.

소수를 구할 때 에라토스테네스의 체에서는 소수의 배수들을 모두 제거했다.

마찬가지로 이 문제에서는 제곱수의 배수들을 모두 제거하면 된다.

문제는 두 가지다.

1. min이 최대 1,000,000,000,000 이 될 수 있다는 점
2. 타임 컷팅

1번은 쉽다.

바로 min과 max 차가 최대 1000000이라는 것이다.

따라서 min과 max차이를 이용하여 배열을 만들어 주면 된다.

min이 index 0이 되도록 한다면 배열의 크기는 아무리 커도 1000000 이하가 될 것이다.

나는 배열을 1부터 시작하도록 만들었고 그렇다면 끝 index는 max - min + 1이 될 것이다.

 

2번에서 많이 헤맸다.

우리는 min부터 제곱수의 배수들을 지우면 된다. 그러면 제곱수를 몇번 곱해야 min이 나오는지를 알기 위해서는 나눗셈을 이용하면 된다.

즉, min / 제곱수 를 이용하여 몇번 곱해야 되는지를 알 수 있다.

그러나, min이 제곱수로 나눠 떨어지지 않는 경우도 있을 것이다. 그럴경우에는 곱하는 횟수를 1 더해줘서 min 다음부터 지우도록 해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	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[1000002];
		Arrays.fill(arr, 1);
		
		for(long i=2;i*i<=max;i++) {
			long pow = i*i;
			long start = min / pow; // min부터 지우기 위해
			if(min % pow != 0)
				start++;
			for(long j=start; j * pow <= max; j++ ) {
				arr[(int) (j * pow - min + 1)] = 0;
			}
		}
		
		int count = 0;
		for(int i=1;i <= max-min+1;i++) {
			if(arr[i] == 1)
				count++;
		}
		
		System.out.print(count);
	}
	
}