[JAVA][Baekjoon] 1456번 거의 소수 🌟🌟🌟🌟🌟

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

📌 접근 방식

에라토스테네스의 체를 활용하여 소수를 구한 뒤, 소수의 N제곱 형태가 범위 [A, B]에 속하는지 확인하는 방식으로 해결했다.

1️⃣ 소수 구하기

• 먼저, 에라토스테네스의 체를 이용해 10,000,000 이하의 모든 소수를 구한다.
• 소수는 나중에 "거의 소수"를 판별하는 데 사용됨

2️⃣ 거의 소수 판별

• 각 소수에 대해 소수를 계속 곱하며 그 값이 범위 [A, B]에 속하면 카운트
• tmp는 소수의 N제곱 값을 저장하며, tmp * arr[i]가 범위를 초과하면 반복을 종료

 

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 받기
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong(); // 범위의 시작 값
        long B = sc.nextLong(); // 범위의 끝 값

        // 10,000,000까지의 소수를 저장할 배열
        long[] arr = new long[10000001];
        for (int i = 2; i < arr.length; i++) {
            arr[i] = i; // 초기화: 인덱스 값을 저장
        }

        // 에라토스테네스의 체로 소수 판별
        for (int i = 2; i <= Math.sqrt(arr.length); i++) {
            if (arr[i] == 0) continue; // 이미 지워진 숫자는 스킵
            for (int j = i + i; j < arr.length; j += i) {
                arr[j] = 0; // 소수의 배수는 지움
            }
        }

        // 거의 소수를 카운트하는 변수
        int count = 0;

        // 소수의 N제곱 값을 구하고 카운트
        for (int i = 2; i < 10000001; i++) {
            if (arr[i] != 0) { // 소수인 경우만 처리
                long tmp = arr[i]; // 소수의 N제곱을 계산할 변수
                while ((double) arr[i] <= (double) B / (double) tmp) { // tmp가 B를 초과하면 종료
                    if ((double) arr[i] >= (double) A / (double) tmp) { // tmp가 A 이상이면 카운트
                        count++;
                    }
                    tmp *= arr[i]; // tmp를 소수로 계속 곱함 (N제곱 계산)
                }
            }
        }

        // 결과 출력
        System.out.println(count);
    }
}

1️⃣ while ((double) arr[i] <= (double)B / (double)tmp)

• 소수의 N제곱 값이 B를 초과하면 반복 종료
• 예를 들어:
  • B = 1000, arr[i] = 2 (소수), tmp = 512라면 2 * 512 = 1024가 B를 초과하므로 종료된다.

2️⃣ if ((double)arr[i] >= (double)A / (double)tmp)

처음에 이 부분이 항상 참처럼 보이는데, false가 나오는 경우는 언제인지 의문을 가졌다.

➡️ 범위의 시작부분을 1일때로 생각해서 그렇게 착각한 것 같다. 1309 처럼 높은 숫자로 시작할 때를 대비한 조건문이다.

• 이 조건은 arr[i] * tmp가 A보다 크거나 같은 경우를 체크하기 위해 사용됩니다.
• 예를 들어:
  • A = 100, arr[i] = 2 (소수), tmp = 32라면 2 * 32 = 64로 A보다 작으므로 false가 됩니다.
  • tmp가 증가하면서 조건이 참이 될 때만 카운트한다

•  

 

😊 느낀 점

이 문제는 너무너무 어려웠다.. 범위가 매우 크기 때문에 효율성을 고려해 구현해야했다.

처음에는 소수의 N제곱을 구하는 과정에서 범위 제한을 어떻게 할지 고민했었는데, while 조건을 통해 처리하는 방식을 사용했다.

소수의 N제곱이 주어진 범위 내에 속하는지를 체크하는 과정이 복잡하게 느껴졌지만, 에라토스테네스의 체를 활용해 소수를 먼저 구하고, 그 후에 제곱해서 범위를 확인하는 방식으로 문제를 해결할 수 있었다.