[백준] 1016 제곱ㄴㄴ수

1. 문제

www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

2. 접근방법

max가 1조

min ~ max 가 최대 100만

 

에라토네스의 채를 응용하여

먼저 소수를 구하고

 

그 소수의 제곱 수로 

저 범위 안의 수를 또 에라토네스의 채 같이 visit 처리를 시키면서

visit 처리가 되어지는 수를 세어

 

전체 갯수에서 빼서 구하면 된다.

 

제곱된 수로 visit을 처리할 때

시작 수를 구하는 것은

 

min이 제곱 수로 나누어 떨어진다면

min부터 시작하고

 

제곱 수로 나누어 떨어지지 않는다면

min / 제곱 수에 +1 한 값을 다시 제곱 수로 곱하면

min보다 크면서 가장 작은 제곱 수의 곱을 구할 수 있다.

 

3. 자바 코드

package Gold;

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

public class G1_1016제곱ㄴㄴ수 {
	static long min,max;
	static int cnt;
	static boolean sqrtvisit[];
	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());
		sqrtvisit = new boolean[(int)(max-min)+1];
		
		eratos((int) Math.sqrt(max));
		System.out.println(max-min-cnt+1);
	}

	static void eratos(int end) {
		boolean visit[] = new boolean[end + 1];
		for (int i = 2; i <= end; i++) {
			if (!visit[i]) {
				eratossqrt(i);
				for (long j = 1L*i * i; j <= end; j += i)
					visit[(int)j] = true;
			}

		}
	}
	
	static void eratossqrt(int num) {
		long numgop = 1L*num*num;
		long start = 0;
		if(min%numgop == 0)
			start = min;
		else
			start =numgop *((min /numgop)+1);

		for(long i = start ; i <= max ; i+=numgop) {
			if(!sqrtvisit[(int)(i-min)]) {
				cnt++;
				sqrtvisit[(int)(i-min)] = true;
			}
		}
	}
}

4. 마치며

에라토네스의 채로 소수를 구하는데

O(N) 이니 100만

그 구해진 100만으로 또 100만개를 검사하니

100만 * 100만으로 터질 거라 생각했는데

 

애초에 소수의 갯수가 적어

100만 + 100만까지 소수의 갯수 * (100만/소수) 라 시간초과는 문제가 없다.

 

소수를 안구하고 그냥 모든 제곱을 구해서 풀이해도 시간초과가 나지 않는다.