[자바] 백준 1837번: 암호제작

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

1837번: 암호제작

 

10의 100승까지 되는 엄청 큰 숫자를 다뤄야 하기 때문에

BigInteger을 사용한다.

 

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

public class P1837 {

	static boolean[] prime = new boolean[1000001];

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		BigInteger num = new BigInteger(st.nextToken());

		int k = Integer.parseInt(st.nextToken());

		for (int i = 2; i < 1000001; i++) {
			prime[i] = true;
		}

		for (int i = 2; i < 1000001; i++) {
			if (prime[i] == true) {
				for (int j = i * 2; j < 1000001; j += i) {
					prime[j] = false;
				}
			}
		}

		for (int i = 2; i < k; i++) {
			if (prime[i] == false)
				continue;

			BigInteger now = new BigInteger(Integer.toString(i));

			if (num.mod(now).compareTo(BigInteger.ZERO) == 0) {
				System.out.println("BAD " + now);
				return;
			}
		}

		System.out.println("GOOD");

	}

}