Maximum Spanning Tree on GCD Complete Graph

ZHY has a complete graph with n vertices numbered from 1 to n. The weight of the edge between vertex u and vertex v is \(\gcd(u,v)\). Your task is to compute the sum of weights of the edges in the maximum spanning tree of this graph.

Hint: For each vertex \(i\) (where \(2 \le i \le n\)), a good strategy is to connect it to a vertex having the maximum possible \(\gcd(i, j)\). It can be shown that connecting vertex \(i\) with its largest proper divisor (i.e. \(\frac{i}{p}\) where \(p\) is the smallest prime factor of \(i\)) yields an optimal solution.

The answer is given by:

[ \text{Answer} = \sum_{i=2}^{n} \frac{i}{\text{spf}(i)},, ]

where \(\text{spf}(i)\) denotes the smallest prime factor of \(i\).

inputFormat

Input Format:

A single integer n (\(1 \le n \le 10^7\)).

outputFormat

Output Format:

Print a single integer, the sum of weights of the maximum spanning tree's edges.

sample

2

1