Codeforces Round #319 (Div. 2) C. Vasya and Petya’s Game

原题: http://codeforces.com/contest/577/problem/C

---

题目大意: 给一个数字n, 一个人猜这个n是多少, 他可以提问: n是不是整除x, 问你最少提问多少次,问的是什么可以猜出n.

---

分析: 算术基本定理(https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). 可以证明,我们需要猜出每个n前边的的质数p, 对于每个p,我们还要猜出其不大于n的倍数, 才能确保n的唯一.

所以答案先晒质数, 再求倍数.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, 2, n + 1, true);
        for (int i = 2; i * i <= n; i++)
            if (prime[i])
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
        int[] primes = new int[n + 1];
        int cnt = 0;
        for (int i = 0; i < prime.length; i++)
            if (prime[i])
                primes[cnt++] = i;
        ArrayList ary = new ArrayList();
        for (int i = 1; i <= n; i++) {
            if (prime[i]){
                for (int j = 1; j <= n; j*=i) {
                    if (i*j > n)
                        break;
                    else
                        ary.add(i*j);
                }
            }
        }
        out.printLine(ary.size());
        out.print(ary.toArray());
    }