• 시간 제한 : 2초, 난이도 : 실버1, 백준 1456번

어떤 수가 소수의 N 제곱(N ≥ 2)일 때 이 수를 ‘거의 소수’라고 한다.

• 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지의 소수를 탐색 해야 한다.

import java.util.Scanner;
public class Practice38 {

	public static void main(String[] args) { //P1456_거의 소수
		Scanner sc = new Scanner(System.in);
		
		long Min = sc.nextLong();
		long Max = sc.nextLong();		
		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];
				while((double)A[i] <= (double)Max /(double)temp) { //A[i] * temp < 범위
					if((double)A[i] >= (double)Min /(double)temp) {
						count++;
					}
					temp = temp * A[i];
				}
			}
		}
		System.out.println(count);
				
		sc.close();
	}
}