[백준 1456] 거의 소수 (Java) - 에라토스테네스의 체

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

거의 소수

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

• 1 ≤ A ≤ B ≤ 1014

예제 입력 1 복사

1 1000

예제 출력 1 복사

25

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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()); // 종료 수

        // 입력 최댓값은 10^14 이므로 최댓값의 제곱근인 10^7까지 소수탐색
        long[] A = new long[10000001];

        for(int i=2; i<A.length; i++){
            A[i] = i;
        }

        // 에라토스테네스의 체 사용하여 소수구하기
        for(int i=2; i<=Math.sqrt(A.length); i++){ // 제곱근까지만 수행
            if(A[i] == 0) continue;
            for(int j = i+i; j<A.length; j=j+i){ // 배수 지우기
                A[j] = 0;
            }
        }

        int count = 0;
        for(int i=2; i<10000001; i++){
            if(A[i] != 0){ // 현재 선택한 수가 소수라면
                long temp = A[i]; // 현재 소수 -> 제곱하면서 거의소수 만들어감

                // N제곱하는 도중 값의 범위가 long형을 초과할 수 있기 때문에
                // N^k , B 비교가 아닌
                // N, B / N^(k-1) 비교로 수행한다.
                while ((double)A[i] <= (double)Max/(double)temp){
                    if((double)A[i] >= (double)Min/(double)temp){
                        count++;
                    }
                    temp *= A[i];
                }
            }
        }
        System.out.println(count);
    }
}

• 에라토스테네스의 체 활용한 문제
• 에라토스테네스의 체
  • 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.
  • 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다.
• 에라토스테네스의 체 원리
  • 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
  • 2부터 시작하고, 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다.
  • 이때 처음으로 선택된 숫자는 지우지 않는다.
  • 배열의 끝까지 반복하고 배열에서 남아있는 모든 수(소수)를 출력한다.

---

문제풀이

• 입력으로 받은 시작수 Min과 종료 수 Max를 받는다.
• 입력 최댓값은 10^1이므로 최댓값의 제곱근인 10^7까지 소수를 탐색한다. -> 에라토스테네스의 체 활용
• '거의소수'를 탐색하기 위해서 아래와 같은 동작을 수행한다.
  • 2~10^7 까지 순회하면서, 현재 선택한 수가 소수라면 현재의 소수를 제곱하면서 거의소수를 만들어간다.
  • N제곱하는 도중 값의 범위가 long형을 초과할 수 있기 때문에 
  • N^k와 Max(or Min)를 비교하는 것이 아닌
  • N과 Max/N^(k-1) 비교를 수행한다.