Форум » Обработка целых чисел » 25 задание задача 153 » Ответить
25 задание задача 153
yana: def p(x): for d in range(2, int(x**0.5)+1): if x%d==0: return False return True for i in range(1,int(1000000**0.25)+1): d=1 b=[] if p(i): if i%d==0: b.append(d) if len(b)==1600: print(i) d=d*2 Непонятно какой диапазон нужно рассматривать
Ответов - 3
Поляков: 1) Для оформления программы воспользуйтесь советом в желтой рамке вверху. 2) Эта задача вот так в лоб не решается. 3) Все решения 25-х задач есть на сайте.
GasDM21: Огромная просьба, добавить разбор алгоритма решения этого задания. Да, на сайте есть решение, можно найти в различных источниках и математическое обоснование - основную теорему арифметики. Особое внимание хотелось бы, чтобы было уделено разбору задач №156 и 157, там где количество делителей является степенью одного простого числа: 729 = 3^6, например. Заранее спасибо.
oval: видимо, в программе на сайте и в ответах ошибка для 729 primeFactors [3,3,3,3,3,3] primes [2,3,5,7,11,13] N=2^2 * 3^2 * 5^2 * 7^2 * 11^2 * 13^2 мы N делим на 13 и умнажаем на 2^3 N=2^5 * 3^2 * 5^2 * 7^2 * 11^2 * 13 но primeFactors станет [6,3,3,3,3,2], а это не 729 и 13 удаляется из primes должно быть primeFactors [9,3,3,3,3] primes [2,3,5,7,11] речь об этом куске кода [pre2] k2 = primeFactors[0] lastPrime = primes[-1] while 2**k2 < lastPrime: N = N // lastPrime * 2**k2 k2 *= 2 del primes[-1] lastPrime = primes[-1] [/pre2] думаю должно быть так: [pre2]k2 = primeFactors[0] lastPrime = primes[-1] while 2**k2 < lastPrime: k = k2 while 2 ** k < lastPrime and primeFactors[-1] - 1 > 0: N = N // lastPrime * 2**k k2 += k primeFactors[-1] -= 1 del primes[-1] del primeFactors[-1] lastPrime = primes[-1][/pre2]
полная версия страницы