[백준] 1016번 제곱ㄴㄴ수

문제 설명

https://www.acmicpc.net/problem/1016

문제 풀이

• 에라토스테네스의 체를 응용하여 풀이하였다.
• 문제 풀이는 다음과 같다.

  1. min~max 값을 저장하는 배열을 생성한다. (최대 길이 10^6)
  2. 특정 숫자의 제곱수의 배수가 해당 범위 내에 있을 때, 그 수의 최대값을 구해줌 (endNum)
  3. (2 ~ endNum) 범위의 수에 대하여 해당 수의 제곱수의 배수 중 min, max 범위에 있는 수들을 하나씩 배열에서 제거해줌

소스 코드 (JAVA)

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

public class Main {
    public static long min, max;
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

    public static void main(String[] args) throws IOException {
        input();
        //배열 생성
        long[] arr = new long[(int)(max - min + 1)];
        //배열 초기화
        long cur = min;
        for (int i = 0; i < max - min + 1; i++)
            arr[i] = cur++;
        //제곱수의 배수가 해당 범위 내에 있을 때, 그 수의 최대값
        int endNum =  (int) Math.floor(Math.sqrt(max));

        for (int i = 2; i <= endNum; i++) {
            long powNum = (long) Math.pow(i, 2);
            cur = powNum * (min % powNum == 0 ? min / powNum : min / powNum + 1);
            while(true) {
                if (cur > max) break;
                //제곱수 제거 시킴
                arr[(int)(cur - min)] = 0;
                cur += powNum;
            }
        }
        int result = 0;
        //결과 출력
        for (int i = 0; i < max - min + 1; i++) {
            if (arr[i] != 0) result++;
        }
        bw.write(result + "\n");
        bw.flush();
    }
}