백준 언더프라임

KIMYEONGJUN·2024년 11월 29일

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 두 정수 A와 B가 주어진다.

첫째 줄에 A보다 크거나 같고,
B보다 작거나 같은 언더프라임 개수를 출력한다.

내가 이 문제를 보고 생각해본 부분

BufferedReader를 사용하여 두 정수 A와 B를 입력받는다.
에라토스테네스의 체를 사용하여 2부터 100,000까지의 소수 여부를 판단한다.
각 정수 i에 대해 소인수를 찾아 소인수의 개수를 세고, 이 개수가 소수인지 확인한다.
소수인 경우 해당 위치에 1을 저장한다.
A 이상 B 이하의 정수 중 언더프라임의 개수를 세어 출력한다.

코드로 구현

package baekjoon.baekjoon_24;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 백준 1124번 문제
public class Main852 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]);
        int B = Integer.parseInt(input[1]);

        // 소수 판별을 위한 배열
        boolean[] isPrime = new boolean[100001];
        int[] primeCount = new int[100001];

        // 에라토스테네스의 체로 소수 구하기
        for(int i = 2; i <= 100000; i++) {
            isPrime[i] = true;
        }

        for(int i = 2; i * i <= 100000; i++) {
            if(isPrime[i]) {
                for(int j = i * i; j <= 100000; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 언더프라임을 체크하기 위한 소인수 개수 세기
        for(int i = 2; i <= 100000; i++) {
            int num = i;
            int count = 0;
            for(int j = 2; j <= num; j++) {
                while(num % j == 0) {
                    count++;
                    num /= j;
                }
                if(num == 1)
                    break;
            }

            if(isPrime[count]) {
                primeCount[i] = 1; // 언더프라임이면 1로 표시
            }
        }

        // A 이상 B 이하의 언더프라임 개수 세기
        int underprimeCount = 0;
        for(int i = A; i <= B; i++) {
            underprimeCount += primeCount[i];
        }

        System.out.println(underprimeCount);
        br.close();
    }
}