BOJ_1016 : 제곱 ㄴㄴ 수

👉 문제링크

1016번: 제곱 ㄴㄴ 수

---

---

🔸 문제 분석 🔸

• 주어진 범위에서 1보다 큰 수의 제곱수로 나누어 떨어지지 않는 수의 개수를 출력한다.
• 최소값이 1부터 1조, 최대값은 최소값부터 100만을 더한 값까지 주어진다.

🔸 문제 풀이 🔸

• min과 max의 값이 1조까지 크게 주어지므로 long으로 받야아 한다.
• 제곱수를 확인하기 위해 에라토스테네스의 체 알고리즘을 사용한다.
  • 배열의 크기를 max-min+1 만큼 차이로 선언한다.
  • 제곱수의 배수를 max까지 계산하며 에라토스테네스의 체 배열에 체크한다.

🔸 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());

        boolean[] pn = new boolean[(int) (max - min + 1)];

        for (long i = 2; i * i <= max; i++) {
            long pow = i * i;
            long start_idx = min / pow;
            if (min % pow != 0) start_idx++;
            for (long j = start_idx; j * pow <= max; j++) {
                pn[(int) ((j * pow) - min)] = true;
            }
        }

        int cnt = 0;

        for (boolean p : pn) {
            if (!p) cnt++;
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• min과 max를 long으로 입력받고, 그 차이만큼 에라토스테네스의 체 배열 pn의 크기로 선언한다.
• 2부터 제곱수가 max를 넘지 않을 때 까지 계산을 반복한다.
  • miin을 제곱수 pow로 나눈 값을 시작 인덱스로 선택하고, 만약 나누어 떨어지지 않는다면 +1한다.
  • pow에 배수가 max를 넘지 않을 때까지 계산해 pn에 체크한다.
• pn에 체크되지 않은 인덱스의 수를 출력한다.

---

🔸 end 🔸

• 에라토스테네스의 체를 알고리즘을 선택하면 어렵지 않게 풀이 할 수 있는 문제이댜.
  • 하지만 min과 max의 범위가 크기 때문에 long을 어떻게 처리하고, start_idx를 선택하는 부분은 고민이 필요했다.