[Java] 백준 1456 거의 소수 - 소수 구하기(2)

백준 1456 거의 소수
문제

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

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

입력

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

출력

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

---

제출

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		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) {
					if((double)A[i] >= (double)Min/(double)temp) {
						count++;
					}
					temp = temp * A[i];
				}
			}
		}
		System.out.println(count);
	}
}

예제

1 1000

 

1 10

 

5324 894739

결과

백준 1456 거의 소수

 

1456번: 거의 소수