백준 1456: 거의 소수

문제 요약

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

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

문제 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

문제 풀이

에라토스테네스의 체를 응용한 문제이다. 우선, 에라토스테네스의 체를 이용하여 소수를 구한 후, a와 b를 소수인 i로 나누어보며 i의 거듭제곱 꼴인 수의 개수를 구한다. 오버플로우가 발생하기 때문에 곱하여 범위를 체크하는 것이 아니라, 나누어가며 범위를 체크한다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {
	static boolean comp[];
	public static void main(String[] args) throws Exception {
		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());
		int n = 10000000;
		comp = new boolean[n + 1];
		double ta, tb;
		long res = 0;
		for(int i = 2; i <= n; i++) {
			if(comp[i] == true) continue;
			for(int j = 2; i * j <= n; j++)
				comp[i * j] = true;
		}
		for(int i = 2; i <= n; i++) {
			if(comp[i]) continue;
			ta = a / (double)i;
			tb = b / (double)i;
			while(i <= tb) {
				if(ta <= i)
					res++;
				ta /= i;
				tb /= i;
			}
		}
		System.out.println(res);
	}
}