Connection Status:
Competition Arena > SimpleMathProblemDiv2

SimpleMathProblemDiv2

TCO19 SRM 741 · 2018-10-30 · by Blue.Mary

TCO19 SRM 741 · 2018-10-30 · by Blue.Mary · Simple Math
Class Name: SimpleMathProblemDiv2
Return Type: long
Method Name: calculate
Arg Types: (int)
Problem Statement

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).

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
0)
1
Returns: 0
1)
2
Returns: 2
2)
3
Returns: 5
3)
4
Returns: 9
4)
5
Returns: 14
7)
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.

Submissions are judged against all 96 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SimpleMathProblemDiv2 with a public method long long calculate(int X) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous