print2161. Зелье Сила чисел

printЗелье Сила чисел

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

На полпути к замку Темного Властелина сэр Петрейн подумал, что негоже идти в гости с пустыми руками. В связи с этим он заглянул к одной своей знакомой ведьме и спросил у нее, что бы такого преподнести Темному Властелину. Ведьма предложила преподнести Темному Властелину кубок, наполненный силой чисел.
Главным ингредиентом этого зелья является кора Темных Дубов, растущих в Темной Роще. Однако не все дубы в Темной Роще – Темные Дубы. А для зелья нужно собрать кору со всех Темных Дубов в Темной Роще. Может возникнуть вопрос: какое же отношение к силе чисел имеют дубы? Спокойствие, сейчас мы все узнаем.
В Темной Роще растут `n` дубов, пронумерованных целыми числами от `1` до `n`. Номера темных дубов обязательно должны делится на самое первое и самое могучее простое число `2`. И не должны делиться на простые числа, превосходящие `3`. Таким образом, дуб является Темным Дубом, если его номер `x` равен числу `2^a\ *\ 3^b`, где `a\ >\ 0,\ b\ ≥\ 0`.
Сэр Петрейн отправил собирать кору своего оруженосца. Тот решил купить телегу для погрузки в нее коры. Причем не слишком большую, чтобы она была не слишком дорога, и не слишком маленькую, чтобы кора в нее влезла. Для этого нужно заранее выяснить, со скольких дубов нужно собрать кору. Помогите это узнать.
Во входном файле записано единственное целое число `n` (`2\ ≤\ n\ ≤\ 10^{18}`).
В выходной файл выведите количество дубов, с которых придется обдирать кору оруженосцу.

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

100

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

15

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

3

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

1
Источник: neerc.ifmo.ru/school
loading