25853번 - Sum of a Function 다국어

Everyone knows that Arup loves prime numbers! This is why he teaches the cryptography course at UCF. Recently, Arup defined the following function on positive integers, n, greater than 1:

f(n) = the smallest prime factor of n

For example, f(14) = 2, f(15) = 3, f(16) = 2 and f(17) = 17.

Using this function, we can generate a sequence of terms f(s), f(s+1), f(s+2), …, f(e), where s designates the starting function input and e designates the ending function input.

Arup thinks these sequences are interesting, but what he’s really curious about is finding the sum of the k minimum elements in one of these sequences. Can you write a program to help him?

Given s, e, and k, find the sum of the k minimum values in the sequence f(s), f(s+1), f(s+2), …, f(e).

The first and only input line will contain three positive integers, s (2 ≤ s ≤ 10¹⁸), e (s+100 ≤ e ≤ s+10⁶), and k (1 ≤ k ≤ 0.9 * (e – s + 1)), representing (respectively) the starting function input, the ending function input, and the number of minimum terms to sum.

On a line by itself, print the sum of the k minimum terms of the designated sequence.

Note: Even though the input specification does not allow “14 17 3” as an input case (i.e., this case will not be in the judge data), it is a simple case that you may want to use for testing purposes – the output (7) can be verified easily on paper. (BTW, the intended solution should solve this case properly anyway.)