GCD Tree
Description:
Teacher Mai has a graph with n vertices numbered from 1 to n. For every edge(u,v), the weight is gcd(u,v). (gcd(u,v) means the greatest common divisor of number u and v).
You need to find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is maximized. Print the total weight of these edges.
Input:
There are multiple test cases(about 105).
For each test case, there is only one line contains one number n(1≤n≤105).
Output:
For each test case, print the answer.
Sample Input:
1 2 3 4 5
Sample Output:
0 1 2 4 5
Source:
Submit