[Java] 백준 1016 제곱 ㄴㄴ 수

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

예제 입력

1 10

예제 출력

7

풀이

수가 굉장히 큰 것 같지만 min 에서 max 사이의 값만 구하면 되므로 1,000,000 의 데이터만 확인하면 된다.

에라토스테네스의 체 알고리즘으로 풀어보자.

코드

import java.util.Scanner;

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

        int min = sc.nextInt();
        int max = sc.nextInt();
        boolean[] arr = new boolean[(max - min + 1)];

        for (long i = 2; i * i <= max; i++) {
            long pow = i * i;
            long start_index = min / max;
            if (min % pow != 0) start_index++;
            for (long j = start_index; pow * j <= max; j++) {
                arr[(int) ((j * pow) - min)] = true;
            }
        }
        int count = 0;
        for (int i = 0; i <= max - min; i++) {
            if (!arr[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}