One of the biggest, most mathematicians would call it THE biggest, unsolved problems in mathematics is the proof of the Riemann Hypothesis: “All non-trivial zeros of the zeta function have real part one- half”. Now your task is simple: For any natural number N, give the N-th zero... nah, just kidding! That would be a much too complex problem for an online contest. We’ll leave Riemann and the zeta function and concern ourselves with the closely related, but much easier to calcultate Mertens’s function. For those interested in the subject I can heartly recommend Derbyshire’s book (see the epilogue). Every positive natural number greater than 1, can be uniquely decomposed into it’s prime factors. Some numbers have only one factor, namely the number itself, like 2, 11 and 71, and are caled prime numbers. Others have more than one factor, like 4 (2×2), 15 (3×5) and 144 (2×2×2×2×3×3), and are called composite numbers. If a number contains all it’s prime factors only once, it is called square free. All prime numbers are square free. Some composite numbers are square free, like 21 (3×7) and 187 (11×17), others are not, like 9 (3×3) and 98 (2×7×7). Let’s define the Mobius function mu(N), for all positive natural numbers N: • mu(1) = 1, by definition; • if N is not square free, mu(N) = 0; • if N is square free and contains an even number of prime factors, mu(N) = 1; • if N is square free and contains an odd number of prime factors, mu(N) = −1. Now we can define Mertens’s function M(N) as the sum of all mu() for 1 up to and including N: M (N ) = mu(1) + mu(2) + . . . + mu(N ). The first 20 values for both functions are in this table: N factors mu(N) M(N) 1-11 2 2 -1 0 3 3 -1 -1 4 22 0 -1 5 5 -1 -2 6 23 1 -1 7 7 -1 -2 8 222 0 -2 9 33 0 -2 10 25 1 -1 11 11 -1 -2 12 223 0 -2 13 13 -1 -3 14 27 1 -2 15 35 1 -1 16 2222 0 -1 17 17 -1 -2 18 233 0 -2 19 19 -1 -3 20 225 0 -3
2/2 We want you to calculate mu(N) and M(N) for some values of N. Input Up to 1000 numbers between 1 and 1000000 (one million), both included, each on a line by itself. The numbers are in random order and can appear more than once. Input is terminated by a line, which contains a single zero. This line should not be processed. Output For each number in the input print that number, the value of mu() for that number and the value of M() for that number, all three on one line, right justified in fields of width 8. The input order must be preserved. Sample Input 20 1 144 73 0 Sample Output 20 0 -3 111 144 0 -1 73 -1 -4