[백준] 1124번. 언더프라임(JAVA)

문제

https://www.acmicpc.net/problem/1124

---

풀이(25분)

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

public class Main {
    static boolean[] prime; // 소수 확인 배열
    static int[] dp; // dp 메모이제이션

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        prime = new boolean[b+1];
        dp = new int[b+1];

        isPrime(b); // 최대 범위까지의 소수 확인

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < b+1; i++){
            if(prime[i]){
                list.add(i);
            }
        } // 소수 리스트

        int answer = 0;

        for(int i = 1; i <= b; i++){
            if(dp[i] == 0){ // dp에 값이 없다면
                for(int prime : list){ // 제일 작은 소수부터 나눠가며 확인
                    if(i % prime == 0){ // 소수로 나누어 떨어진다면
                        dp[i] = dp[i/prime] + 1; // 소수로 나눈 값의 + 1
                        break;
                    }
                }
            }
        }

        for(int i = a; i <= b; i++){
            if(prime[dp[i]]){
                answer++;
            }
        }


        System.out.println(answer);

    }

    public static void isPrime(int n){ // 에라토스테네스의 체
        for(int i = 0; i < n+1; i++){
            prime[i] = true;
        }
        prime[0] = false;
        prime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if(!prime[i]){
                continue;
            }
            dp[i] = 1;
            for(int j = i * i; j <= n; j *= i){ // 소수의 제곱수들 체크
                dp[j] = dp[j/i] + 1;
            }
            for(int j = i*i; j <= n; j += i){
                prime[j] = false;
            }
        }

    }
}

 

에라토스테네스의 체를 응용해서 해결한 문제이다.

에라토스테네스의 체를 모른다면 https://to-travel-coding.tistory.com/83 글을 참고하자.

 

먼저 에라토스테네스의 체로 전체 범위의 소수를 모두 확인해 준다.

이때 소수의 제곱수들까지 dp배열에 저장해 준다.

 

dp 배열을 이용하는 것은 다음과 같다.

1. 문제에서 소인수분해를 진행해야 한다.

2. 소인수분해를 진행하는 과정에서 소수로 나눌 수 있다면, 이 전값의 +1만 해주면 된다.

 

따라서 소수를 모두 확인한 뒤 1~b까지 전체 범위에 대한 dp 값을 저장한다.

 

이후 최종적으로 문제 조건에 맞게 dp[i]가 소수인지 확인하여 정답을 출력한다.