Недавно Филипп вышел на завод с необычным графиком работы. Смена Филиппа на заводе будет длиться дней, при этом каждый из дней, у которого ровно 9 делителей, считается выходным. Посчитайте, сколько выходных будет у Филиппа за одну смену на заводе. Формат

Нам нужно посчитать, сколько чисел от 1 до n имеют ровно 9 делителей. Для этого разберём, каким свойствам должно удовлетворять натуральное число, чтобы число его делителей было равно
9.

Шаг 1. Анализ разложения на множители и число делителей

Если число имеет разложение на простые вида
  a = p1^α1 ⋅ p2^α2 ⋅ … ⋅ pk^αk,
то число его делителей равно
  (α1 + 1)⋅(α2 + 1)⋅ … ⋅ (αk + 1).

Чтобы это число стало равным 9, нужно, чтобы произведение было равно 9. Заметим, что 9 = 9⋅1 = 3⋅3, а потому возможны два случая:
 • один из по...