자바로 백준 1124 풀기

풀이)
에라토스테네스의 체를 활용하여 소수를 구한다.
DP 리스트를 만들어 해당하는 수가 소수로 나누어지는지 확인하고 i가 j로 나누어진다면, DP[i] = DP[i / j] + 1이다. 작은 수부터 탐색하기 때문에 값이 벗어나는 경우는 없다.
DP에 저장된 소인수 개수는 HashSet을 활용하여 소수인지 확인한다.

내 코드)

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

public class Main {
    public static void main(String[] args) {
        try {
            int n,m,cnt = 0;
            HashSet <Integer> hs = new HashSet<>();
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            
            // 소인수 개수를 저장할 dp 리스트
            int [] dp = new int[m + 1];
            
            // 에라토스테네스의 체를 위해 필요한 boolean 리스트
            boolean [] oTable = new boolean[m + 1];
            
            // 에라토스테네스의 체
            Arrays.fill(oTable, true);
            for(int i = 2; i <= m; i ++){
                if(oTable[i] == true){
                    hs.add(i);
                    int cur = i * 2;
                    while(cur <= m){
                        oTable[cur] = false;
                        cur += i;
                    }
                }
            }
            
            // DP 업데이트
            for(int i = 2; i <= m; i ++) {
                for (Integer j : hs) {
                    if(i % j == 0){
                        dp[i] = dp[i / j] + 1;
                        break;
                    }
                }
            }
            for (int i = n; i <= m; i++) {
                if(hs.contains(dp[i])){
                    cnt++;
                }
            }
            System.out.println(cnt);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}