[백준] 1837번 암호제작 (JAVA)

문제

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

1837번: 암호제작

 

설명

어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다.
두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 

먼저 K보다 작은 소수를 에라토스테네스의 체를 이용해 구한다.

P가 구한 소수들에 나누어 떨어지는지 확인하고 하나라도 있다면 break를 하여 빠져나온다.

boolean[] checked = new boolean[K + 1];

for (int i = 2; i <= K; i++) {
    if (!checked[i]) {
        for (int j = i * 2; j <= K; j += i) {
            checked[j] = true;
        }
    }
}

for (int i = 2; i < K; i++) {
    if (!checked[i])
        divide(P, i);

    if (smaller != 0) 
        break;
}

여기서 4 ≤ P ≤ \( 10^{100} \) 이기 때문에 P를 char[] 배열에 담아 저장한다. ( int 자료형의 범위 ≤ \( 10^{10} \) )

divide 함수에서는 char[] 배열의 원소를 divider과 나누면서 나누어 떨어지는지 확인한다.

static void divide(char[] P, int divider) {
    int r = 0;
    for (char c : P) {
        int pos = c - '0';
        r = (pos + r * 10) % divider;
    }

    if (r == 0)
        smaller = divider;
}

 

전체 코드

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

public class Main {

    static char[] P;
    static int K;
    static boolean[] checked;
    static int smaller = 0;

    static void divide(char[] P, int divider) {
        int r = 0;
        for (char c : P) {
            int pos = c - '0';
            r = (pos + r * 10) % divider;
        }

        if (r == 0)
            smaller = divider;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        P = st.nextToken().toCharArray();
        K = Integer.parseInt(st.nextToken());

        checked = new boolean[K + 1];
        for (int i = 2; i <= K; i++) {
            if (!checked[i]) {
                for (int j = i * 2; j <= K; j += i) {
                    checked[j] = true;
                }
            }
        }

        for (int i = 2; i < K; i++) {
            if (!checked[i])
                divide(P, i);

            if (smaller != 0)
                break;
        }

        if (smaller == 0)
            System.out.println("GOOD");
        else
            System.out.println("BAD " + smaller);
    }
}