MMFMOB - Möbius function
In number theory and combinatorics Möbius function μ(n) for integer n > 0 is defined as follows:
μ(1) = 1
μ(n) = (-1)k if n is the product of k (k > 0) distinct primes
μ(n) = 0 otherwise.
Given integer n > 0 compute μ(n).
Note: 11/06/2018 added new test case.
Input
Each line of input contains one random integer number 1 ≤ n ≤ 108 (100 000 000). Input terminates with 0 (zero). There will be two input files.
Output
For each n print μ(n) value on new line.
Example
Input: 1 2 3 4 5 6 0 Output: 1 -1 -1 0 -1 1
Added by: | julkas |
Date: | 2018-05-15 |
Time limit: | 60s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |