printЛето 7

printG. Простая сумма

Ограничения: время – 1s/2s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Константин каждую пятницу ходит на факультатив по информатике, где частенько разбираются вполне занимательные задачки. Например:
Пусть функция `F(K)`, где `K` – натуральное число, задана следующим образом: `F(K)=F(K_1)+F(K_2)`, если `K=K_1*K_2` (`K_1\ >\ 1`, `K_2\ >\ 1`), `F(K)=K`, если `K` – простое, и `F(1)=0`, то есть `F(K)` – сумма чисел в разложении числа `К` на простые множители. Например, `F(12)=2+2+3=7`, так как `12=2*2*3`.
Ввод
Дано число `N` (`1\ ≤\ N\ ≤\ 10\ 000\ 000`).
Вывод
Вывести `(F(1)+F(2)+…+F(N-1)+F(N))\ mod\ 2^30`.

Пример ввода

12

Пример вывода

63
Источник: Турнир "Экспонента-2006"
loading