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

Реализация на Python--

import datetime

import time

from math import sqrt

 

UTC = datetime.datetime.utcnow

 

class MyClass:

    def __init__(self, number):

       self.number = number

       self.res = 0

       self.acc = [[1]]

 

    def addToPos(self, pos, i):

        self.acc[pos] = self.acc[pos] + [i]

 

    def addToTail(self, i):

        self.acc = self.acc + [[i]]

 

    def testPos(self, pos, i):

        ret = True

        for x in self.acc[pos]:

            if i % x == 0:

                ret = False

                break

        return ret

 

    def addCand(self, i):

        ret = False

        pos = 0

        for lst in self.acc:

          if self.testPos(pos, i):

            ret = True

            self.addToPos(pos, i)

            break

          pos = pos + 1

 

        if not ret:

            self.addToTail(i)

 

 

    def calc(self):

        for i in range(2, self.number + 1):

            self.addCand(i)

        print(self.acc)

        print(len(self.acc))

 

def test(num):

   start = UTC()

  

   cl = MyClass(num)

   cl.calc()

 

   print (UTC() - start)

 

if __name__ == '__main__':

    test(int(input()))

    

   ----python test.py9[[1], [2, 3, 5, 7], [4, 6, 9], [8]]4

# Код на ruby 2.2.3p173a = []a << [1]for i in 2..10001    f = 0    a.each{ |group|        m = 1        group.each { |c|            m *= i % c        }        f += m        if m > 0            group << i            break        end    }    a << [i] if f == 0endp ap a.size