[BOJ] [JAVA] 1016번 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수

한 달 전에 풀었지만 소수 문제를 몇 번 더 풀어본 후 다시 풀어봤다.(근데 내가 예전에 푼 풀이랑 기가 막히게 똑같다 ㅋㅋ)

이 문제의 핵심은 for문에서 <첫번째 제곱 ㄴㄴ 수를 어떻게 잡을 것인가>라고 생각한다.

start보다 큰 첫 i * i배수를 아래와 같이 잡았다. 나누기를 통해 몫을 구하고 다시 (i * i)를 곱해서 (i * i)의 배수를 만들었다.

이렇게 된다면 a는 항상 start보다 작거나 같은 (i * i)의 배수일 것이다.

만약 a < start라면 a += i * i를 통해 start보다 큰 (i * i)의 배수로 만들어 주었다.

long a = start / (i * i) * (i * i);
if (a != start) a += i * i;
// a는 start보다 큰 (i * i)의 배수

이후는 에라토스테네스의 체와 동일하다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long start = sc.nextLong();
		long fin = sc.nextLong();
		
		boolean [] arr = new boolean[(int) (fin - start + 1)];
		
		
		for (long i = 2; i <= Math.sqrt(fin); i++) {
			long a = start / (i * i) * (i * i);
			if (a != start) a += i * i;
			
			while (a <= fin) {
				arr[(int) (a - start)] = true;
				a += i * i;
			}
		}
		int ans = 0;
		for (boolean b : arr) {
			if(!b) ans++;
		}
		
		System.out.println(ans);
	}

}