[백준] 1016 제곱 ㄴㄴ 수

 

 

---

https://chanhuiseok.github.io/posts/baek-16/

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

https://girawhale.tistory.com/40

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

 

 

---

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

public class Main {
	static boolean[] prime = new boolean[1000001];
	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());
		isPrimeNumber();
		System.out.println(result(min, max));
	}
	//에라토스테네스의 체
	static void isPrimeNumber() {
		for(int i = 2; i < Math.sqrt(1000000); i++) {
			if(prime[i])
				continue;
			for(int j = i * i; j <= 1000000; j += i) {
				prime[j] = true;
			}
		}
	}
	static int result(long min, long max) {
		boolean[] ch = new boolean[(int) (max-min+1)]; //max와 min의 최대 차는 1000000이다.
		int ans = (int) (max-min+1); //탐색해야 하는 수의 개수
		for(long i = 2; i * i <= max; i++) { //long으로 해줘야한다 i * i 때문
			if(prime[(int) i]) //소수가 아닌건 제외 
				continue;
			long start = i * i; //max보다 작은 제곱수
			
			long sNum = min / (i * i); //구하려는 수 start와 곱했을 때 min보다 커야함
			if(min % (i*i) != 0) { 
				sNum += 1;
			}
			
			while(sNum * start <= max) {
				if(!ch[(int) (sNum * start - min)]) {
					ch[(int)(sNum * start - min)] = true; //제곱으로 나누어 떨어지는 수 4 9 16...
					ans -= 1;
				}
				sNum += 1; // 30 100 경우 8~25 * start 값을 골라준다
			}
		}
		return ans;
	}
}