문제 설명

문제 분석

슈도코드

구현

public class 거의_소수_구하기_1456 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long A = scan.nextInt();
        long B = scan.nextInt();
        long[] arr = new long[10000001];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = i;
        }

        // 모든 소수를 먼저 구함
        for (int i = 2; i <= Math.sqrt(arr.length); i++) { // 제곱근 까지만 수행
            if (arr[i] == 0) continue;

            for (int j = i + i; j < arr.length; j += i) { // 배수 지우기
                arr[j] = 0;
            }
        }

        int count = 0;
        for (int i = 2; i < 10000001; i++) {
            if (arr[i] != 0) {
                long temp = arr[i];
                // 곱셈이 long의 범위를 넘어갈 수 있어 이항 정리로 처리
                while ((double) arr[i] <= (double) B / (double) temp) { // 2 <= 1000 / 2 <= 500
                    if ((double) arr[i] >= (double) A / (double) temp) {
                        System.out.println(temp * arr[i] + " ");
                        count++;
                    }
                    temp *= arr[i];
                }

            }
        }

        System.out.println(count);
    }
}