[백준] 1016 제곱 ㄴㄴ 수

[문제 링크]

1016번: 제곱 ㄴㄴ 수

 

import java.util.*;

public class Main {
	static int count = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long min = sc.nextLong();
		long max = sc.nextLong();

		boolean[] check = new boolean[1000001];
		long end = (long)Math.sqrt(max);

        //에라토스테네스의 체 원리
		for(long i = 2; i < end+1; i++) {
			long temp = i*i;
			long start = 0;
			if(min % temp == 0) {
				start = min / temp;
			}else {
				start = (min / temp) + 1;
			}
			for(long j = start; j*temp < max+1; j++) {
				check[(int)((j*temp)-min)] = true;
			}
		}

		for(int i = 0; i < (max-min+1); i++) {
			if(check[i]==false) {
				count++;
			}
		}
		System.out.println(count);
	}
}

이번 문제는 겉보기에 쉬워보였고, for문과 if문을 통해 쉽게 구현했지만 문제가 있었다.

바로 시간초과이다..❕이는 for문을 여러번 돌고  min, max의 숫자 자체가 커서 생기는 오류였다.

 

이를 해결하기 위해서는 '에라토스테네스의 체 원리' 를 사용해야 한다.

에라토스테네스의 체 원리란, 소수를 빠르게 찾는 방법이다. 
2부터 시작하게 될 경우, 차례대로 소수의 배수를 제거한다. (이때, 본인은 제거하지 않는다.)
이를 반복하면 최종적으로 모든 소수가 남는다.

 

에라토스테네스 체 원리에 대한 쉬운 이해와 설명은 아래의 블로그를 참고하길 바란다.

[JAVA] 소수 찾기 - 에라토스테네스의 체

 

이 문제에서는 boolean 타입의 check 배열을 만들어 소수를 체크할 수 있도록 하였고,

입력값을 min = 1, max = 10으로 주었을 때, 가장 작은 제곱수인 4를 시작으로

min을 4로 나누었을 때, 나누어 떨어지면 start의 값을 몫으로, 그렇지 않으면 몫 + 1값을 가져가도록 하고, 

지금은 min의 값이 1이므로 start = 1이된다.

1*4 = 4이고, 4는 1~10 사이의 값이므로 check 배열의 해당 인덱스 값을 ture로 지정한다.

그 이후 제곱수의 수를 늘려가며 반복하고 최종적으로 check 배열의 값이 false인 제곱 ㄴㄴ수의 수를 출력하면 된다.