Topcoder SRM 517 div2 medium "CompositeSmash"

ある数字と目的となる数字が与えられる．その数字を２つの数の積で表すということを繰り返していき，その中の一つに目的となる数字がすべてのパターンにおいて存在しうるかどうかを求める．

とりあえず積で表せるものをすべて見ていったらいいかなと思って実装．本番中には実装間に合わなかった．

public class CompositeSmash {

	public String thePossible(int N, int target) {
		if(N == target){
			return "Yes";
		}else if(N < target){
			return "No";
		}
		for(int i = 2; i < N; ++i){
			if(N % i == 0 && thePossible(i, target).equals("No") && thePossible(N / i, target).equals("No")){
				return "No";
			}
		}
		return "Yes";
	}

}