tc - 517 div1 - 250 (java)

CompositeSmash.java

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

public class CompositeSmash
{
    HashMap<Integer, Boolean> _cache = new HashMap();
    boolean possible(int n, int t) {
        if (n < t) return false;
        if (n == t) return true;
        if (_cache.containsKey(n)) return _cache.get(n);

        boolean res = true;
        int count = 0;
        for (int i = 2; i*i <= n; i++)
            if (n % i == 0) {
                count++;
                res &= possible(i, t) || possible(n/i, t);
                if (not(res)) break;
            }
        res &= count != 0;
        _cache.put(n, res);
        return res;
    }

    public String thePossible(int N, int target) {
        return possible(N, target) ? "Yes" : "No";
    }

    void main() throws IOException {
        int n;
        while ((n = nextInt()) != EOF) {
            int t = nextInt();
            _cache.clear();
            out.println(thePossible(n, t));
        }
    }

    public static void main(String[] args) {
        new CompositeSmash().run();
    }

    // ======================================================================

    int inf = Integer.MAX_VALUE;
    final int EOF = -1;

    boolean not(boolean p) { return !p; }

    int sqr(int x) { return x*x; }
    long sqr(long x) { return x*x; }
    double sqr(double x) { return x*x; }

    BufferedReader fin;
    StringTokenizer st;
    PrintWriter out;

    public void run() {
        try {
            fin = new BufferedReader(new InputStreamReader(System.in));
            st = null;
            out = new PrintWriter(System.out);
            main();
            fin.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = fin.readLine();
            if (line == null) return "-1";
            else st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
}