[JAVA]백준 1837번: 암호제작

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

1837번: 암호제작

1. 문제 설명

 

두 소수 p, q의 곱 P를 비밀 키로 두었을 때 p, q 중 하나라도 K 보다 작다면 BAD와 암호를 이루는 가장 작은 수 출력.

아니라면 GOOD 출력

 

 

2. 풀이

 

암호 P의 범위가 10^100까지 이므로 int/long이 아니라 String으로 입력을 받아서 큰 수 나눗셈을 해야 한다.

 

미리 에라토스테네스의 체로 K의 범위(10^6)까지 소수를 구별해놓고, 앞에서부터 순서대로 P를 나누어보면 된다.

 

*로직

- 에라토스테네스의 체로 소수 구별

- 2부터 K보다 작은 수 까지 큰 수 나눗셈 진행

 

3. 코드

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

public class Main {

    public static boolean[] check = new boolean[1000001];
    public static String P;
    public static int K;
    public static int size;
    public static char[] P_char;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int sum = 0;

        // 소수 계산
        for (int x = 2; x <= 1000000; x++) {

            if(check[x])
                continue;

            for (int y = 2 * x; y <= 1000000; y += x) {

                check[y] = true;
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());

        P = st.nextToken();
        K = Integer.parseInt(st.nextToken());

        size = P.length();
        P_char = P.toCharArray();

        int ans = find();

        if (ans == -1) {
            System.out.println("GOOD");
        } else {
            System.out.println("BAD " + ans);
        }
    }

    public static int find() {

        int ans = -1;

        for (int x = 2; x < K; x++) {
            if (!check[x] && divide(x)) {
                ans = x;
                return ans;
            }
        }

        return ans;
    }

    public static boolean divide(int x) {

        int mid = 0;

        for (int idx = 0; idx < size; idx++) {
            mid = mid * 10 + P_char[idx] - '0';

            mid %= x;
        }

        return mid == 0;
    }




}