Badly implemented sieve of Eratosthenes

Time limit1sMemory limit512 MB

Summary

Count how many times the inner statement runs in a nested loop where the outer index i goes from 1 to n and the inner step is i, for n up to 10^9.

Level: Easy3 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

Seongwon implemented the sieve of Eratosthenes in C++ from memory after class. Hyeongseok, sitting next to him, said the code was wrong, and the two decided to count how many times line 6 runs. Given $n$ , compute that count.

The code is as follows.

int n;
cin >> n; // read n
int* sieve = new int[n + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        sieve[j] += 1; // line 6
    }
}

The outer loop runs $i$ from $1$ to $n$ . The inner loop starts $j$ at $1$ and adds $i$ while $j$ does not exceed $n$ . Line 6 is the body of the inner loop, and the task is its total execution count.

Input

The first line contains a natural number $n$ with $1 \le n \le 10^9$ .

Output

Print the total number of executions of line 6 on the first line.

Examples3

Example 1
Input
```
3
```
Expected output
```
6
```
Example 2
Input
```
12
```
Expected output
```
41
```
Example 3
Input
```
1560
```
Expected output
```
13253
```