백준 - 1456: 거의 소수

문제

---

1456번: 거의 소수

 

풀이

---

💡 제가 푼 방법보다 더 좋은 방법이 있을 수 있습니다. 이렇게 푸는게 항상 정답은 아니니 참고하셔야 합니다.

 

범위는 1 ~ 10¹⁴로 입력값을 담는 타입은 long을 이용해야 합니다.

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());

 

우선 소수를 구해야 거의 소수를 알 수 있기 때문에 소수부터 구해봅시다.

 

구해야되는 소수의 범위는 1 ~ B라고 생각할 수 있지만, 문제에서 구하라는 것은 '거의 소수'입니다.

소수의 n제곱수들을 구하는 것이기 때문에 구할 수 있는 소수 중에 가장 큰 소수의 제곱이 B를 넘지 않아야합니다.

 

식으로 나타내면 다음과 같습니다.

• p : 소수
• p² ≤ B → P ≤ √B

 

소수를 구하려는 범위가 정해졌다면, 에라토스테네스의 체를 이용하여 아래와 같이 소수를 구합니다.

public static boolean[] findPrime(long n) {

   // 입력 값의 최대치인 10^14를 루트를 씌우면 10^7이므로 int 범위 내라 배열 크기로 잡을 수 있음
   int range = (int)Math.sqrt(n);

   boolean[] noPrime = new boolean[range + 1];

   noPrime[0] = noPrime[1] = true;

   for (int i = 2; i <= Math.sqrt(range); i++) {
      if (!noPrime[i]) {
         for (int j = i + i; j <= range; j += i) {
            noPrime[j] = true;
         }
      }
   }

   return noPrime;
}

 

소수를 구했다면, 소수의 n제곱수들을 구해야할 차례입니다.

 

소수의 n제곱 값이 long타입을 벗어날 수 있으니 이항정리를 통해 식을 정리하여 넘지 않아도 구할 수 있도록 해줍니다.

boolean[] noPrime = findPrime(B);

int cnt = 0;

// 거의 소수를 구하기 위해 구한 소수들을 순회
for (int i = 2; i < noPrime.length; i++) {
   // 소수라면
   if (!noPrime[i]) {
      long nearPrime = i;

      /**
       *     소수의 n제곱 값이 long타입을 벗어날 수 있으므로 이항 정리로 정리하여 처리합니다.
       *     A <= p^n <= B , n >= 2
       *     -> A/p^(n-1) <= p <= B/p^(n-1) , n >= 2
          */
      while ((double) i <= (double) B / (double) nearPrime) {
         if ((double) i >= (double) A / (double) nearPrime) {
            cnt++;
         }

         nearPrime *= i;
      }
   }
}

 

전체 코드는 다음과 같습니다.

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


public class Main {

   public static void main(String[] args) throws IOException {

      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());

      boolean[] noPrime = findPrime(B);

      int cnt = 0;

      // 거의 소수를 구하기 위해 구한 소수들을 순회
      for (int i = 2; i < noPrime.length; i++) {
         // 소수라면
         if (!noPrime[i]) {
            long nearPrime = i;

            /**
             *     소수의 n제곱 값이 long타입을 벗어날 수 있으므로 이항 정리로 정리하여 처리합니다.
             *     A <= p^n <= B , n >= 2
             *     -> A/p^(n-1) <= p <= B/p^(n-1) , n >= 2
             */
            while ((double) i <= (double) B / (double) nearPrime) {
               if ((double) i >= (double) A / (double) nearPrime) {
                  cnt++;
               }

               nearPrime *= i;
            }
         }
      }
      System.out.println(cnt);
   }

   public static boolean[] findPrime(long n) {

      // 입력 값의 최대치인 10^14를 루트를 씌우면 10^7이므로 int 범위 내라 배열 크기로 잡을 수 있음
      int range = (int)Math.sqrt(n);

      boolean[] noPrime = new boolean[range + 1];

      noPrime[0] = noPrime[1] = true;

      for (int i = 2; i <= Math.sqrt(range); i++) {
         if (!noPrime[i]) {
            for (int j = i + i; j <= range; j += i) {
               noPrime[j] = true;
            }
         }
      }

      return noPrime;
   }
}