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

Codeforces Round #319 (Div. 2) C. Vasya and Petya's Game | 书脊
http://codeforces.com/contest/577/problem/C

Vasya and Petya are playing a simple game. Vasya thought of number x between 1 and n, and Petya tries to guess the number.

Petya can ask questions like: "Is the unknown number divisible by number y?".

The game is played by the following rules: first Petya asks all the questions that interest him (also, he can ask no questions), and then Vasya responds to each question with a 'yes' or a 'no'. After receiving all the answers Petya should determine the number that Vasya thought of.

Unfortunately, Petya is not familiar with the number theory. Help him find the minimum number of questions he should ask to make a guaranteed guess of Vasya's number, and the numbers yi, he should ask the questions about.

原题: 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());

    }

Read full article from Codeforces Round #319 (Div. 2) C. Vasya and Petya's Game | 书脊