Итак, нужно найти число групп, в каждой из которых ни одно из чисел не делит все остальные.
Строим группы так: (1) - 1 (2) - 2, 3, 5, 7, 11, 13... - все простые (3) - 4, 6, 9, 10, 14, 15... - произведения двух простых ... (k) - произведения (k - 1) простых
И так пока не кончатся все числа. Поскольку в каждой группе наименьшее число 2^(k - 1), то k - минимальное, для которого 2^(k - 1) > N
По построению явно во всех группах ни одно число не делится на другое. Осталось проверить, что получено минимальное число групп. Это очевидно: числа 1, 2, 4, ..., 2^(k-1) должны быть в разных группах.
Решение: n = int(input()) t = 1 k = 0 while t <= n: t *= 2 k += 1 print(k)
--
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