백준 1016 제곱 ㄴㄴ수 <G1>

간단해 보여서 단계가 높지만 풀어보았다.

X가 1보다 큰 제곱수로 안나뉘면 '제곱 ㄴㄴ수'라고 칭하는데 제곱수는 정수의 제곱으로 입출력이 굉장히 크기에 효율성이 중요한 문제라고 생각이 들었다. 최대한 빠르게 소수를 판별하는 알고리즘을 찾아봤다.

 

아레토스테네스의 체 가 있었다.

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

간단하게 정리하면 2부터 원하는 범위까지의 수를 나열하고 소수를 우측에 써가며 해당하는 배수를 모두 지우는 방식이다. 예시의 범위가 120까지인데 11^2 > 120 이므로 11보다 작은 배수만 지워도 충분한게 장점이다. 2,3,5,7 의 배수만 지우면 모두 소수이기 때문이다. 이전의 값들은 선행으로 처리되므로 반복연산의 시작점이 달라 효율적이라고 할 수 있다.

 

그렇다면 연산의 시간복잡도는 Max -min 의 모든 수에서 제곱수를 구하는 연산이 필요했는데

Max의 제곱수 보다 작은 소수로 제곱하면 모든 소수 제곱수를 알 수 있게 되었다.

 

import java.util.*;
 
public class Main { //  1016번 백준 제곱근 ㄴㄴ
    public static void main(String[] args) throws Exception {
        //input
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();
        long size = max-min + 1; // 범위 설정
        boolean[] prime = new boolean[(int)size];
        long i = 2;
        
        //logic
        while (i * i <= max) { // Max보다 작은 제곱까지
            long sqrt = i * i; // 제곱근
            int correction = 0; // 보정값
            if (min % sqrt != 0) { // 제곱근으로 나눠지지 않는다면
                correction = 1;
            }
            //min 이상인 첫번째 제곱수의 배수 구하기
            long data = (min / sqrt) + correction;
            while (sqrt * data <= max) { // 범위
                // 소수 체크 판별
                if (!prime[(int)(sqrt * data - min)]) {
                    prime[(int)(sqrt * data - min)] = true;
                    size -= 1; // 지우기
                }
                data += 1; // 배수 증가
            }
            
            i += 1; // 다음번째로 증가
        }
        // output
        System.out.println(size);
    }
}

// Logic

Max보다 작은 제곱수까지 반복한다.

제곱근으로 min을 나눴을때 나눠지지 않는다면 보정값 1을 주어 다음수로 넘어간다. -> 불필요한 연산을 피하기 위함

범위 내의 소수 * data가 prime [] 배열에 체크되어 있지 않다면 체크하고 size -- 을 통해 일반 수를 지운다.

이후 data ++ 로 배수를 증가시키고 다음 제곱수를 연산한다.