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

🔗 문제 링크

BOJ 1016번: 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수

 

📝 풀이 과정

min과 max 사이에서 1이 아닌 제곱수로 나누어떨어지지 않는 수를 찾는 문제이다.
min과 max의 범위가 $10^{12}$으로 굉장히 크기 때문에 하나씩 조사하는 것은 불가능하댜.

 

어떻게 시간을 줄일 수 있을까 고민을 하던 중 범위 내에서 '소수 제곱'의 배수를 제거해준다면 훨씬 빠르게 제거가 가능할 것이라는 생각이 들었다.

 

 

for (int i = 2; i <= 1000000; i++) {
  if (prime[i]) {
      for (int j = 2; i * j <= 1000000; j++)
          prime[i * j] = false;
    }
}

max의 제곱근은 최대 1,000,000까지이므로 해당 범위 내의 소수를 '에라토스테네스의 체'로 구하였다.

 

 

boolean[] ck = new boolean[(int) (max - min + 1)];
for (long i = 2; i * i <= max; i++) {
    if (!prime[(int) i])
        continue;

    long square = i * i;
    for (long j = min / square + (min % square != 0 ? 1 : 0); j * square <= max; j++) {
        if (!ck[(int) (j * square - min)]) {
            ck[(int) (j * square - min)] = true;
        }
    }
}

다음으로 min ~ max까지의 범위 내에서 제곱ㄴㄴ수인지 판별하는 ck배열을 만들었다. 해당하는 숫자를 인덱스로 둘 경우 범위를 초과하지만 max와 min의 차는 1,000,000이므로 숫자에서 - min을 한 결과는 int 범위 내이므로 (int)로 강제 형변환을 해준다.

 

소수가 아닐 경우 패스하고, 소수의 제곱에 j 배 만큼의 수들을 제곱ㄴㄴ수가 아니라고 체크하였다.
j의 시작 범위는 long j = min / square + (min % square != 0 ? 1 : 0)로 설정하였는데, min % square != 0이라면 나누어 떨어지지 않아 소수점 아래 자리수가 버림되므로 square값과 j를 곱해도 min보다 결과값이 작아지게 되어 오류가 발생할 수 있기 때문에 +1을 해주었다.

 

이후, ck 배열에서 true가 아닌 값은 제곱ㄴㄴ수이므로 해당하는 갯수를 세어준다.

 

💻 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong(), max = sc.nextLong();

        boolean[] prime = new boolean[1000001];
        Arrays.fill(prime, true);
        prime[1] = false;

        for (int i = 2; i <= 1000000; i++) {
            if (prime[i]) {
                for (int j = 2; i * j <= 1000000; j++)
                    prime[i * j] = false;
            }
        }

        boolean[] ck = new boolean[(int) (max - min + 1)];
        for (long i = 2; i * i <= max; i++) {
            if (!prime[(int) i])
                continue;

            long square = i * i;
            for (long j = min / square + (min % square != 0 ? 1 : 0); j * square <= max; j++) {
                if (!ck[(int) (j * square - min)]) {
                    ck[(int) (j * square - min)] = true;
                }
            }
        }

        int cnt = 0;
        for (long i = min; i <= max; i++)
            if (!ck[(int) (i - min)])
                cnt++;

        System.out.println(cnt);

    }
}

 

📊 제출 결과