함수의 합

모두가 Arup이 소수를 좋아한다는 것을 안다. 그래서 그는 UCF에서 암호학 강의를 맡고 있다. 최근 Arup은 1보다 큰 양의 정수 $n$에 대해 다음 함수를 정의했다.

$f(n) = n\text{의 가장 작은 소인수}$

예를 들어 $f(14) = 2$, $f(15) = 3$, $f(16) = 2$, $f(17) = 17$이다.

이 함수를 이용하면 $f(s), f(s+1), f(s+2), \ldots, f(e)$라는 수열을 만들 수 있다. 여기서 $s$는 시작 입력값, $e$는 끝 입력값이다.

Arup은 이런 수열이 흥미롭다고 생각하지만, 실제로 알고 싶은 것은 수열에서 가장 작은 $k$개 원소의 합이다. 이 합을 구하는 프로그램을 작성하라.

$s$, $e$, $k$가 주어지면 수열 $f(s), f(s+1), f(s+2), \ldots, f(e)$에서 가장 작은 $k$개 값의 합을 구하라.

첫 번째이자 유일한 입력 줄에 양의 정수 $s$, $e$, $k$가 이 순서대로 주어진다. 이들은 다음 조건을 만족한다.

$2 \le s \le 10^{18}, \quad s+100 \le e \le s+10^{6}, \quad 1 \le k \le 0.9 \cdot (e - s + 1).$

수열에서 가장 작은 $k개$ 항의 합을 한 줄에 출력한다.

입력 조건상 $s=14$, $e=17$, $k=3$인 경우는 허용되지 않으므로 채점 데이터에는 없다. 다만 답 $7$을 종이에서 쉽게 확인할 수 있는 간단한 경우이므로 테스트용으로 써 볼 만하다. 의도된 풀이는 이 경우도 올바르게 처리해야 한다.