Размещено 4 года назад по предмету Информатика от mike45388

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

Ответ на вопрос

Ответ на вопрос дан hambis

Реализация на 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.py
9
[[1], [2, 3, 5, 7], [4, 6, 9], [8]]
4
Ответ на вопрос

Ответ на вопрос дан Aillianna

# Код на ruby 2.2.3p173
a = []
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 == 0
end

p a
p a.size