백준 1016: 제곱 ㄴㄴ 수

문제 요약

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

문제 분류

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

문제 풀이

에라토스테네스의 체를 응용한 문제이다. max와 min값이 크지만, 사실 그 사이의 개수를 세면 되므로 n을 그 차로 두어 제곱ㄴㄴ수의 개수를 센다. 그리고 제곱수만 true로 표시하고, 제곱수가 아닌 수의 개수를 세어 출력하면 된다.

풀이 코드

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

public class Main {
	static boolean isN[];
	static long min, max;
	static int n, res;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		min = Long.parseLong(st.nextToken());
		max = Long.parseLong(st.nextToken());
		n = (int)(max - min) + 1;
		isN = new boolean[n];
		long sq, start, temp;
		for(long i = 2; ; i++) {
			sq = i * i;
			start = min / sq + ((min % sq > 0) ? 1 : 0);
			temp = sq * start;
			if(sq > max) break;
			while(temp <= max) {
				isN[(int)(temp - min)] = true;
				temp += sq;
			}
		}
		for(int i = 0; i < n; i++)
			if(!isN[i]) res++;
		System.out.println(res);
	}
}