SimpleMathProblemDiv2 | Topcoder Archive

Problem Statement

The function g(n, p) is defined for all positive integers n and all primes p. Its definition is as follows:

if n is not divisible by p:
    g(n,p) = 0
otherwise:
    g(n,p) = the largest power of p that does not exceed n

The function f(n) is defined for all positive integers as follows: f(n) is the sum of g(n,p) over all primes p.

You are given an int X. Compute and return the exact value of the sum f(1) + f(2) + ... + f(X).

Definition

Class:: SimpleMathProblemDiv2
Method:: calculate
Parameters:: int
Returns:: long
Method signature:: long calculate(int X)
(be sure your method is public)

Notes

You may assume (and also see from the Examples) that the largest possible output fits into a long.

Constraints

X will be between 1 and 444,777, inclusive.

Examples

```
1
```
```
Returns: 0
```
```
8
```
```
Returns: 36
```
Note that f(6) = 7, because g(6,2) = 4 and g(6,3) = 3. If you think that g(6,2) should be 2, please go back and re-read the definition of g more carefully.
```
15
```
```
Returns: 128
```
```
77444
```
```
Returns: 3296580744
```
```
444777
```
```
Returns: 111293895799
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.