[백준 1016] 제곱 ㄴㄴ 수 / 자바 / 수학(에라토스테네스의 체)

#문제         

레벨: G1
알고리즘: 수학(에라토스테네스의 체)
풀이시간: 1시간
힌트 참조 유무: 유

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

 

---

#문제 풀이        

에라토스테네스의 체 문제를 한 번이라도 풀어본 사람이라면 이 문제를 보자마자 그 문제라는 것을 직감할 것이다. 다른 방식으로 찾게 된다면, 시간복잡도에서 걸리기 때문입니다. 

체에서 알 수 있듯이 에라토스테네스의 체는 제한 숫자내에서 2,3,...의 제곱들을 미리 걸러주는 것는 것입니다. 만약 4의 차례가 왔다면 앞서 2의 제곱으로 이미 걸러졌기 때문에 4는 탐색을 안 하고 패스되는 것입니다.

이 문제는 소수를 찾는 것이 아니고 어떤 숫자의 제곱으로 나눠지나 안 나눠지나 판단하는 에라토스테네스체의 응용문제입니다.

---

#풀이 코드      

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        
        boolean[] isSquareFree = new boolean[(int)(max - min + 1)];
        Arrays.fill(isSquareFree, true);
        
        for (long i = 2; i * i <= max; i++) {
            long square = i * i;
            //min도 포함해야 하므로 min -1를 해준다.
            long start = ((min - 1) / square + 1) * square;
            
            for (long j = start; j <= max; j += square) {
                isSquareFree[(int)(j - min)] = false;
            }
        }
        
        int count = 0;
        for (boolean b : isSquareFree) {
            if (b) count++;
        }
        
        System.out.println(count);
    }
}