06/04/2025 16:25:52

Рабочее место участника

Задачи

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

Ограничения: время – 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$ .

Пример ввода

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

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

03/07/2008	Лето 2008 дорешивание ( 7G)
16/07/2008	Лето 2008 - 7 (G)