문제

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

해설

이 문제를 이해하려면 10~20까지의 배열을 기준으로 생각해라

2부터 제곱인 수를 통해 입력한 범위 값이 제곱으로 나누어 지지 않는 수를 찾으면 된다.

1. 에리토스 테네스의 체를 통해 포문의 범위를 2부터 Math.sqrt(max)까지 지정한다.

for (long i =2; i<= Math.sqrt(max); i++)

2. i값을 시작 값의 목을 구한다음 조건을 통해 +1을 해준다.

long startNum = min/pow;
if(min%pow != 0){
	startNum++; 
}

이유는 이렇다 만약 10부터 시작일때 pow가 2라면 10/2 5이므로 startNum값은 5가 된다. 하지만 pow가 4라면 10/2 2이므로 이 값은 8이 되며 시작값인 10보다 작은 값이 된다. 그러므로 +1을 해줘서 시작값을 12로 만들어 줘야 한다.

3. 시작값을 구했다면 끝나는 값을 max/pow를 해줘서 이중 포문으로 해당 구간을 반복한다.

for(int i = 0; i<check.length; i++)

4. 반복하는 동안 check 배열로 제곱수에 해당하는 인덱스를 true로 입력한다.

check[(int)(j*pow-min)] = true;

5. 이후 포문을 돌면서 false인 수를 세어보고 이를 cnt에 담아 출력한다.

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

코드

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

public class J1016_0 {
    public static void main(String[] args) throws IOException {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));

        String[] input = buffer.readLine().split(" ");

        long min = Long.parseLong(input[0]);
        long max = Long.parseLong(input[1]);
        int cnt = 0;

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


        for(long i =2; i<= Math.sqrt(max); i++){
            long pow = i*i;
            long startNum = min/pow;
            if(min%pow != 0){
                startNum++;
            }
            for(long j = startNum; j<=max/pow; j++){
                check[(int)(j*pow-min)] = true;
            }
        }
        
        for(int i = 0; i<check.length; i++){
            if(!check[i]){
                cnt++;
            }
        }
        
        System.out.println("cnt = " + cnt);
    }
}