2635:The Embarrassed Cryptographer

keyword

BruteForce　素数　素因数分解　Java

概要

K(<10^100)とL(<10^6)が与えられたときKがL以下の素因数を持つかどうかを求める問題。Lが小さいので全探索可能。ただしmodの計算にコストがかかるはずなので素数リストは作っておく必要がある。

import java.util.*;
import java.math.*;

class Main {

	static int sz = 78498;
	static BigInteger primes[] = new BigInteger[sz];

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		seive(1000000);
		while(true){
			BigInteger k = in.nextBigInteger(), l = in.nextBigInteger();
			BigInteger a = BigInteger.ZERO;
			if(k.equals(BigInteger.ZERO)) break;
			for(BigInteger p : primes){
				if(p.compareTo(l) >= 0){
					break;
				}
				else if(k.mod(p).equals(BigInteger.ZERO)){
					a = p;
					break;
				}
			}
			if(a.equals(BigInteger.ZERO)) System.out.println("GOOD");
			else System.out.println("BAD " + a);
		}
	}

	private static void seive(int n){
		int pos = 0;
		boolean list[] = new boolean [n+1];
		for(int i=2; i<=n; i++) list[i] = true;
		for(int i=2; i<=n; i++)if(list[i]){
			primes[pos++] = new BigInteger(Integer.toString(i));
			for(int j=2*i; j<=n; j+=i) list[j] = false;
		}
	}
}