1230: Подільність -> Тренування для ТЮІ-2017


Submit solution


Points:5
Time limit:0.5s
Memory limit:64M
Author:

Problem type

Сьогодні в школі на уроці математики проходять подільність чисел. Щоб продемонструвати властивості подільності, учитель виписав на дошці всі цілі числа від 1 до N в кілька груп. При цьому, якщо одне число ділиться на інше, то вони обов'язково виявилися в різних групах. Наприклад, якщо взяти N = 10, то вийде 4 групи.
Перша група: 1.
Друга група: 2, 7, 9.
Третя група: 3, 4, 10.
Четверта група: 5, 6, 8.
Ви вже здогадалися, що, оскільки будь-яке число ділиться на 1, одна група завжди буде складатися тільки з числа 1, але інші розбиття можна виконати різними способами. Від вас вимагається визначити мінімальне число груп, на яке можна розбити всі числа від 1 до N відповідно за наведеною вище умовою.

Формат вихідних даних

Програма отримує на вхід одне натуральне число N, яке не перевищує 109

Формат вихідних даних

Повинна вивести одне число - шукану мінімальну кількість груп.

Приклад вхідних даних

10

Приклад вихідних даних

4

Comments


  • 0
    Aradam
     commented on Nov. 1, 2017 edited

    Цю задачу вирішив, випадково, не думаючи навіть. Завжди люблю розглядувати цифри в двійковій системі.


    • 0
      zvit
       commented on Nov. 2, 2017 edited

      класний розв'язок ;)