Найти число от 1 до n имеющее максимальное число делителей

@Pythonistj · 04.12.2022, 16:21. **Показов** 4231. **Ответов** 17

Студворк — интернет-сервис помощи студентам

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
-------------------------------------------------------------
Задано число n. Требуется найти число от 1 до n, включительно, которое имеет
максимальное число положительных целых делителей.
Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12.
-------------------------------------------------------------
Формат входных данных
На вход подается одно число n (1 ≤ n ≤ 109**3)
-------------------------------------------------------------
Формат выходных данных
Выведите на первой строке число от 1 до n, включительно, которое имеет мак-
симальное число делителей. На второй строке выведите число его делителей.
Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите
любое из них.
------------------------------------------------------------
Примеры
standard input
20
standard output
12
6

@Pythonistj · 04.12.2022, 19:15 **[ТС]**

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
-------------------------------------------------------------
Задано число n. Требуется найти число от 1 до n, включительно, которое имеет
максимальное число положительных целых делителей.
Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12.
-------------------------------------------------------------
Формат входных данных
На вход подается одно число n (1 ≤ n ≤ 10⁹**3)
-------------------------------------------------------------
Формат выходных данных
Выведите на первой строке число от 1 до n, включительно, которое имеет мак-
симальное число делителей. На второй строке выведите число его делителей.
Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите
любое из них.
------------------------------------------------------------
Примеры
standard input
20
standard output
12
6

@Gdez · 04.12.2022, 20:12

n ≤ 109**3

Это чуть больше $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ ?
Тогда - простой перебор по простым числам согласно формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?\prod ({p}_{i} + 1)$

@Catstail · 05.12.2022, 06:29

Pythonistj, 10⁹**3 = 10²⁷. Не думаю, что Питон справится с такой задачей за отведенные 2 сек.

@Catstail · 05.12.2022, 08:29

Gdez, думаю, что имеется в виду 10⁹**3=10²⁷. Да, это немного больше, чем 10⁶

@Gdez · 05.12.2022, 09:27

Catstail, Тогда пас

@Red white socks · 05.12.2022, 10:49

Catstail, Вообще-то справится.
Числа с большим числом делителей имеют определенную структуру...

@Gdez · 05.12.2022, 16:58

для (1, 10**27) максимальное количество делителей у числа > 1 000 000 или ~ 2**21...

@Red white socks · 05.12.2022, 18:48

Gdez, как вам вариант 1 ≤ n ≤ 10**(9**3)?

@Gdez · 05.12.2022, 20:59

Red white socks, вроде нашел
Число - 22994910221505295561488000
Число делителей - 2097152
Для 10**27

Для 10**(9**3) получилось
9471553213125585133875304923003298482961 6588432897758201756996327162580806715367 4314801247800440080124112111396193010995 5564753895965494693758815036349077906788 6437231632162886294473533172997531062046 5459091976197629272811752263285193883532 0056138203560404151175532404168897590543 8791673402138184346795762118798554588941 5364266749858466091286055184182702639740 6574083921143596327872902826465431739316 3089185104802242158310771424706381945355 9340775830581945675845681524098728339382 2501120384303312329967943627132471814841 8270539453665927022676673985450433718395 1528833528725562449429273605896891033808 2862865567897051041944048691068669363420 2661806150369390114092081893289213973369 2956118741308625047947668400640000000

1897137590064188545819787018382342682267 9754287618550012224730563856487160207114 24
Но здесь возможна ошибка - вместо деления пришлось применить целочисленное деление

@Red white socks · 05.12.2022, 21:40

Сообщение от Gdez

Число - 22994910221505295561488000

Gdez, это число можно как минимум в три или в четыре раза увеличить.
Тут разновидность рюкзака.
ТС интереса к задаче не проявил, поэтому особо детали не продумывал.
Посмотрю завтра, если время будет.

@Gdez · 05.12.2022, 21:42

Red white socks, по условию - любое число с максимумом делителей. Применил алгоритм поиска не самого числа, а количества делителей (в комментарии выше <= 2^21). От этого количества находил минимально возможное число. Если оно больше заданного, то число делителей уменьшал на 1. И так, пока не будет меньше N...

@Red white socks · 06.12.2022, 17:00

Сообщение от Gdez

Red white socks, вроде нашел
Число - 22994910221505295561488000
Число делителей - 2097152
Для 10**27

Последовательность (k1,k2,...) назовем подходящей, если

$https://www.cyberforum.ru/cgi-bin/latex.cgi?k_1\geq k_2\geq k_3 \geq \ldots$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?N \geq \prod p_i^{k_i}$ ,
(p_i) - последовательность простых.

Перебором по всем подходящим последовательностям максимум = 4128768. Достигается на 2 числах:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?872164094829950853082152000 = 2^6 \cdot 3^5 \cdot 5^3 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47 \cdot 53 \cdot 59$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?975641190826724683108848000=2^7 \cdot 3^6 \cdot 5^3 \cdot 7^2 \cdot 11^2 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47 \cdot 53$

@Gdez · 06.12.2022, 17:08

Red white socks, Поэтому и "вроде"

. Позже "пришел" ко второму числу, начинающемуся с 9... через отношение 10^27//найденное число с добавлением к найденному новых степеней.
А еще позже понял, что быстрее просто перебирать степени делителей до числа < N с последующей сортировкой и фильтром, убирая числа с меньшим количеством делителей у меньшего числа...

@Red white socks · 06.12.2022, 17:23

По поводу 10**729.

Сообщение от Red white socks

Тут разновидность рюкзака

Пусть у нас неограниченное есть число мешков. Предметы из i-го мешка весят log(p_i). В каждом мешке предметы со стоимостью log(2), log(3/2), log(4/3) и так далее (для каждой стоимости ровно один предмет). Требуется набрать предметы с максимальной стоимостью с ограничением веса log(N).

Не покидает ощущение, что для N=10**729 она решается на питоне в пределах минуты (секунда для плюсов).
Из большинства мешков у нас будет один предмет...
Но решения у меня пока нет

@Pythonistj · 06.12.2022, 17:27 **[ТС]**

тут 109 в 3 степени макс ограничение - это 1295029

Добавлено через 12 секунд
это не 10 в 9, это 109

@Red white socks · 06.12.2022, 18:28

Gdez, что думаете, реально ее будет решить?

Добавлено через 13 минут
Pythonistj,

Python
1
2
3
4
5
6
hcn =[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 
      240, 360, 720, 840, 1260, 1680, 2520, 5040, 
      7560, 10080, 15120, 20160, 25200, 27720, 45360, 
      50400, 55440, 83160, 110880, 166320, 221760, 277200, 
      332640, 498960, 554400, 665280, 720720, 1081080]
print(max(x for x in hcn if x <= N))

Добавлено через 41 минуту
Там еще и число делителей нужно.
Тогда так:

Python
1
2
3
4
5
6
7
8
9
10
res = [(1, 1),(2, 2),(4, 3),(6, 4),(12, 6),(24, 8),(36, 9),
       (48, 10),(60, 12),(120, 16),(180, 18),(240, 20),(360, 24),
       (720, 30),(840, 32),(1260, 36),(1680, 40),(2520, 48),
       (5040, 60),(7560, 64),(10080, 72),(15120, 80),(20160, 84),
       (25200, 90),(27720, 96),(45360, 100),(50400, 108),
       (55440, 120),(83160, 128),(110880, 144),(166320, 160),
       (221760, 168),(277200, 180),(332640, 192),(498960, 200),
       (554400, 216),(665280, 224),(720720, 240),(1081080, 256)]
 
print(max(x for x in res if x[0]<=N), sep='\n')

@Gdez · 06.12.2022, 18:59

Red white socks,

Численно в 2 сек только 10^120 уложился... Если переделать в numpy будет быстрее, но ес-но все равно не плюсики

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

Найти число от 1 до n имеющее максимальное число делителей

Решение

Решение

@Pythonistj Заблокирован

	Найти число от 1 до n имеющее максимальное число делителей 04.12.2022, 16:21. Показов 4231. Ответов 17 Метки нет (Все метки) Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт ------------------------------------------------------------- Задано число n. Требуется найти число от 1 до n, включительно, которое имеет максимальное число положительных целых делителей. Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12. ------------------------------------------------------------- Формат входных данных На вход подается одно число n (1 ≤ n ≤ 109**3) ------------------------------------------------------------- Формат выходных данных Выведите на первой строке число от 1 до n, включительно, которое имеет мак- симальное число делителей. На второй строке выведите число его делителей. Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите любое из них. ------------------------------------------------------------ Примеры standard input 20 standard output 12 6 0

@Pythonistj Заблокирован
	04.12.2022, 19:15 [ТС]
	Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт ------------------------------------------------------------- Задано число n. Требуется найти число от 1 до n, включительно, которое имеет максимальное число положительных целых делителей. Например, если n = 20, то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6, 12. ------------------------------------------------------------- Формат входных данных На вход подается одно число n (1 ≤ n ≤ 10⁹**3) ------------------------------------------------------------- Формат выходных данных Выведите на первой строке число от 1 до n, включительно, которое имеет мак- симальное число делителей. На второй строке выведите число его делителей. Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите любое из них. ------------------------------------------------------------ Примеры standard input 20 standard output 12 6 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,740 Записей в блоге: 14
	05.12.2022, 06:29
	Pythonistj, 10⁹**3 = 10²⁷. Не думаю, что Питон справится с такой задачей за отведенные 2 сек. 1

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,740 Записей в блоге: 14
	05.12.2022, 08:29
	Gdez, думаю, что имеется в виду 10⁹**3=10²⁷. Да, это немного больше, чем 10⁶ 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.12.2022, 09:27
	Catstail, Тогда пас 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	05.12.2022, 10:49
	Catstail, Вообще-то справится. Числа с большим числом делителей имеют определенную структуру... 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.12.2022, 16:58
	для (1, 1027) максимальное количество делителей у числа > 1 000 000 или ~ 221... 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	05.12.2022, 18:48
	Gdez, как вам вариант 1 ≤ n ≤ 10(93)? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.12.2022, 20:59
	Red white socks, вроде нашел Число - 22994910221505295561488000 Число делителей - 2097152 Для 1027 Для 10(9**3) получилось 9471553213125585133875304923003298482961 6588432897758201756996327162580806715367 4314801247800440080124112111396193010995 5564753895965494693758815036349077906788 6437231632162886294473533172997531062046 5459091976197629272811752263285193883532 0056138203560404151175532404168897590543 8791673402138184346795762118798554588941 5364266749858466091286055184182702639740 6574083921143596327872902826465431739316 3089185104802242158310771424706381945355 9340775830581945675845681524098728339382 2501120384303312329967943627132471814841 8270539453665927022676673985450433718395 1528833528725562449429273605896891033808 2862865567897051041944048691068669363420 2661806150369390114092081893289213973369 2956118741308625047947668400640000000 1897137590064188545819787018382342682267 9754287618550012224730563856487160207114 24 Но здесь возможна ошибка - вместо деления пришлось применить целочисленное деление 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	05.12.2022, 21:42
	Red white socks, по условию - любое число с максимумом делителей. Применил алгоритм поиска не самого числа, а количества делителей (в комментарии выше <= 2^21). От этого количества находил минимально возможное число. Если оно больше заданного, то число делителей уменьшал на 1. И так, пока не будет меньше N... 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	06.12.2022, 17:08
	Red white socks, Поэтому и "вроде" . Позже "пришел" ко второму числу, начинающемуся с 9... через отношение 10^27//найденное число с добавлением к найденному новых степеней. А еще позже понял, что быстрее просто перебирать степени делителей до числа < N с последующей сортировкой и фильтром, убирая числа с меньшим количеством делителей у меньшего числа... 1

@Pythonistj Заблокирован
	06.12.2022, 17:27 [ТС]
	тут 109 в 3 степени макс ограничение - это 1295029 Добавлено через 12 секунд это не 10 в 9, это 109 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	06.12.2022, 18:59
	Сообщение было отмечено Pythonistj как решение Решение Red white socks, Численно в 2 сек только 10^120 уложился... Если переделать в numpy будет быстрее, но ес-но все равно не плюсики 2