[Java] 백준 22943번 수

브루트포스, 수학 문제입니다.

조건에 맞는 수가 몇개있는지 찾아야합니다.

1. K가지의 숫자로 이루어진 수
=> (K가 3인 경우, 100~999까지의 수 중에서 숫자가 겹치지 않는 수들 (101, 110, 373, 888 등 제외)
2. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
3. 1번의 수들 중 M으로 나누어 떨어지지 않을 때 까지 나눈 수가 소수의 곱인 경우
=> 나누어 떨어지지 않을 때 : M이 5인 경우,  (9 => 9), (10 => 2), (24 => 24), (25 => 1), (30 => 6)

코드 진행 순서
1. 소수를 찾기.
2. 소수의 합으로 만들 수 있는 값들 찾기
3. 소수의 곱으로 만들 수 있는 값들 찾기
4. M으로 나누어 떨어진 수가 3번에 해당하는지 찾기
5. 위의 조건에 해당하는 수가 K가지 숫자로 이루어진 수인지 확인

위의 조건을 만족하는 경우 카운팅해주고 출력해주었습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int k = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int result = 0;
    boolean isPrime = true;
    ArrayList<Integer> al = new ArrayList<>();
    int[] arr = new int[100001];

    for (int i = 2; i < Math.pow(10, k); ++i) {
      isPrime = true;
      for (int j = 0; j < al.size(); ++j) {
        if (i % al.get(j) == 0) {
          isPrime = false;
          break;
        }
      }

      if (isPrime) {
        al.add(i);
      }
    }

    for (int i = 0; i < al.size(); ++i) {
      for (int j = i + 1; j < al.size(); ++j) {
        int add = al.get(i) + al.get(j);

        if (add >= 100000) {
          break;
        }

        arr[add] = 1;
      }
    }

    for (int i = 0; i < al.size(); ++i) {
      for (int j = i; j < al.size(); ++j) {
        long mul = (long) al.get(i) * (long) al.get(j);

        if (mul < 100_000) {
          arr[(int) mul] |= 2;
        }
      }
    }

    for (int i = (int) Math.pow(10, k - 1); i < Math.pow(10, k); ++i) {
      int bit = 0;
      int num = i;
      int div = i;

      if ((arr[i] & 1) == 0) {
        continue;
      }

      while (div % m == 0) {
        div /= m;
      }

      if ((arr[div] & 2) != 0) {
        arr[i] = 7;
      } else {
        continue;
      }

      for (int j = 0; j < k; ++j) {
        if ((bit & (1 << (num % 10))) != 0) {
          bit = 0;
          break;
        }

        bit |= (1 << (num % 10));
        num /= 10;
      }

      result = bit != 0 ? result + 1 : result;
    }

    bw.write(result + "\n");
    bw.close();
  }
}