[백준 자바] 1016번(제곱 ㄴㄴ수)

난이도 - 골드 1

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

 

---

 

728x90

min~max의 수가 제곱수의 배수인지 나타내는 배열을 생성한다.(isNoeSquares)

outerLoop: 2부터 루트max까지의 i의 제곱수를 계산한다.(square)

                  innerLoop의 시작점을 계산한다. min이 square로 나누어 떨어지면 start는 min이 되고, 그렇지 않으면 min보다 큰 수 중 가장 작은 square의 배수를 start로 한다.

innerLoop: min부터 max까지 square의 배수들을 true로 변경한다.

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

public class Main1016 {
  public static void main(String[] args) throws Exception {
    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());

    bw.write(String.valueOf(countNotSquare(min, max)));

    bw.flush();
    br.close();
    bw.close();
  }

  static int countNotSquare(long min, long max) {
    boolean[] isNotSquares = new boolean[(int) (max - min + 1)];

    for (long i = 2; i * i <= max; i++) {
      long square = i * i;
      long start = min % square == 0 ? min : min + (square - min % square);

      for (long j = start; j <= max; j += square) {
        isNotSquares[(int) (j - min)] = true;
      }
    }

    int count = 0;

    for (int i = 0; i < isNotSquares.length; i++) {
      if (!isNotSquares[i]) {
        count++;
      }
    }

    return count;
  }
}