ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1816. Проблемы с Поллардом

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Однажды Александр решил изучить метод Полларда. Однако он плохо разобрался в теории и в результате написал следующий алгоритм разложения числа n на простые множители:
  1. Если n простое, вернуть n.
  2. В противном случае, выбрать случайное r из отрезка [1, 1018] и вычислить g — наибольший общий делитель n и r.
  3. Если g = 1 или g = n, повторить шаг 2, в противном случае рекурсивно вызвать алгоритм для чисел g и n/g и вернуть объединение полученных списков множителей.
Александру стало интересно, сколько раз для данного числа n в процессе работы алгоритма будет вычислен наибольший общий делитель на шаге 2. Помогите ему узнать это.

Исходные данные

В единственной строке записано целое число n (2 ≤ n ≤ 109).

Результат

Выведите единственное число — ожидаемое количество раз, которое будет вычислен наибольший общий делитель, с абсолютной или относительной погрешностью не более 10−6.

Примеры

исходные данныерезультат
12
4.8571428571
8
6.6666666667
Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010