[JAVA] 백준 1456 에라토스테네스의 체

 

 

 

1456번: 거의 소수

문제

소수의 제곱(N ≥ 2)으로 표현할 수 있는 수를 “거의 소수”라고 한다.

구간 A와 B가 주어졌을 때 A이상 B이하의 거의 소수를 구하여라

1 ≤ A ≤ B ≤ $10^{14}$

풀이

먼저 에라토스테네스의 체를 활용하여 소수를 모두 구한 후 계산하였다.

에라토스테네스의 체

        // 100,000,000,000,000 -> (10,000,000)^2 즉 천만의 제곱까지만 구하면 거의 소수를 구할 수 있다.
        boolean[] X = new boolean[10000001];
        for(int i=2; i<Math.sqrt(X.length); i++){
            if(!X[i]) {
                for (int j = i + i; j < X.length; j += i) {
                    X[j] = true;
                }
            }
        }

$10^{14}$의 범위를 모두 커버하기 위해서 $10^7$까지의 모든 소수를 구하였다.

“거의 소수” 구하기

        // 거의 소수 -> A와 B사이에 있고 소수의 제곱인 수
        // 수가 크기때문에 수를 단순화 시킨다

        int answer = 0;
        for (int i = 2; i < X.length; i++) {
            if (!X[i]) {
                                // N^k-1 (k >= 2)
                long now = i;
                        // N^k <= B -> N <= B / N^k-1
                while ((double)i <= (double) B / (double) now) {
                                        // N^k >= A -> N >= A / N^k-1
                    if ((double) i >= (double) A / (double) now) {
                        answer++;
                    }
                                        // 제곱
                    now *= i;
                }
            }
        }

전체 코드

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

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 A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        // 100,000,000,000,000 -> (10,000,000)^2 즉 천만의 제곱까지만 구하면 거의 소수를 구할 수 있다.
        boolean[] X = new boolean[10000001];
        for(int i=2; i<Math.sqrt(X.length); i++){
            if(!X[i]) {
                for (int j = i + i; j < X.length; j += i) {
                    X[j] = true;
                }
            }
        }

        // 거의 소수 -> A와 B사이에 있고 소수의 제곱인 수
        // 수가 크기때문에 수를 단순화 시킨다.
        // N^k <= B -> N <= B / N^k-1
        // N^k >= A -> N >= A / N^k-1
        int answer = 0;
        for (int i = 2; i < X.length; i++) {
            if (!X[i]) {
                long now = i;
                while ((double)i <= (double) B / (double) now) {
                    if ((double) i >= (double) A / (double) now) {
                        answer++;
                    }
                    now *= i;
                }
            }
        }
        System.out.println(answer);
    }
}

결과