Найти число по количеству делителей

@gray621 · Регистрация: 14.01.2021

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

Формат ввода
Вводится натуральное число – количество делителей, считая единицу и само число.

Формат вывода
Вывести наименьшее число с таким количеством делителей.

Пример 1
Ввод Вывод
8
24
Пример 2
Ввод Вывод
48
2520
Примечания
При решении нельзя использовать функции и методы, а также списки и словари.

Вот код, чтобы найти кол-во делителей числа, а как наоборот?

Python
1
2
3
4
5
6
7
8
9
10
n = int(input())
count_of_dividers = 0
 
for i in range(n - 1, 1, -1):
 
    if n % i == 0:
 
        count_of_dividers += 1
 
print(count_of_dividers)

@unfindable_404 · 17.01.2021, 20:32

На основе вашего кода:

Python
1
2
3
4
5
6
7
8
9
10
11
divs = int(input())
n = 1
while True:
    count_of_dividers = 0
    for i in range(n, 0, -1):
        if n % i == 0:
            count_of_dividers += 1
    if count_of_dividers == divs:
        print(n)
        break
    n += 1

@Gdez · 17.01.2021, 20:42

gray621, подсказка - количество делителей :
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\prod_{}^{}({{p}_{i}}^{} + 1)$
Где $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{i}$ - степень простого i-го множителя в составе исходного числа
24 -> 2*2*2*3 -> $https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{3} * {3}^{1}$
Итого множителей = (3+1) * (1+1) = 8

@gray621 · 17.01.2021, 20:52 **[ТС]**

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

divs = int(input())
n = 1
while True:
count_of_dividers = 0
for i in range(n, 0, -1):
if n % i == 0:
count_of_dividers += 1
if count_of_dividers == divs:
print(n)
break
n += 1

Спасибо, у меня не получалось придумать ещё n, а так всё такое же.

Добавлено через 5 минут

Python
1
2
3
4
5
6
7
8
9
10
11
divs = int(input())
n = 1
while True:
    count_of_dividers = 0
    for i in range(n, 0, -1):
        if n % i == 0:
            count_of_dividers += 1
    if count_of_dividers == divs:
        print(n)
        break
    n += 1

Код не работает на 18 тесте, превышен лимит времени, можно как-то ускорить цикл?

@Gdez · 17.01.2021, 21:06

gray621, ограничения на "n" есть ?

@gray621 · 17.01.2021, 21:23 **[ТС]**

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

ограничения на "n" есть ?

Нет, но есть ограничение на время 1 секунда, а тест идёт 1064 ms, то есть нужно ускорить цикл немножко.

Добавлено через 15 минут
Я думаю можно уменьшить время пополам если уменьшить в range number пополам, т.к. делителей больше половины числа нет. Как это реализовать если в range int?

@Arsegg · 17.01.2021, 21:35

Нарыл решение

Но оно не удовлетворяет условию:

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

При решении нельзя использовать функции и методы, а также списки и словари.

В т. ч. мемоизация.

@Gdez · 17.01.2021, 22:08

gray621, если не ошибся

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
divs = int(input())
if divs % 2 :
    n = 1
    while True:
        if int(n**0.5) == n**0.5 :
            count_of_dividers = 1
            for i in range(1, int(n**0.5)):
                if n % i == 0:
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 1
else :
    n = divs
    while True:
        if int(n**0.5) != n**0.5 :
            count_of_dividers = 0
            for i in range(1, int(n**0.5) + 1) :
                if n % i == 0 :
                    count_of_dividers += 2
            if count_of_dividers == divs:
                print(n)
                break
        n += 2

Добавлено через 7 минут
Arsegg, на кодфорсе как то набрел на задачку по делителям. Вроде решил - тесты все прошла. Но позже сам нашел при каких N неверно считает мой код. Там через плюсики с реккурсией решили.
Если интересует, то возможно найду задачу на кодфорс. А тут я выкладывал тему :
Разложение на множители

@Arsegg · 17.01.2021, 22:34

Не по теме:

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

Если интересует, то возможно найду задачу на кодфорс.

Полагаю, задача div1. :D

@gray621 · 17.01.2021, 22:49 **[ТС]**

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

divs = int(input())
if divs % 2 :
n = 1
while True:
if int(n**0.5) == n**0.5 :
count_of_dividers = 1
for i in range(1, int(n**0.5)):
if n % i == 0:
count_of_dividers += 2
if count_of_dividers == divs:
print(n)
break
n += 1
else :
n = divs
while True:
if int(n**0.5) != n**0.5 :
count_of_dividers = 0
for i in range(1, int(n**0.5) + 1) :
if n % i == 0 :
count_of_dividers += 2
if count_of_dividers == divs:
print(n)
break
n += 2

А почему там n в корень возводится, а не пополам делится?

Добавлено через 5 минут
Зачем проверка

Python
1
if int(number ** 0.5) == number ** 0.5

?

@Gdez · 17.01.2021, 23:11

Arsegg,

Не по теме:

нет. Нашел https://codeforces.com/contest... bile=false

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

А почему там n в корень возводится, а не пополам делится?

Потому что это не слагаемые, а делители. Допустим для 40 не нужно искать делители больше 6, сразу считать парами - 1 и 40, 2 и 20, 4 и 10, 5 и 8; всего 8 делителей.
Первый while перебирает квадраты чисел - у них нечетное число делителей.
Поэтому и проверка (это ответ на второй вопрос) - если число не квадрат другого числа, то количество делителей четное

Добавлено через 5 минут
gray621, Кроме 1, остальные минимальные числа с заданным количеством делителей - четные. Поэтому, если N > 1, то счетчик можно с шагом 2 по четным числам

@gray621 · 17.01.2021, 23:25 **[ТС]**

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

если число не квадрат другого числа, то количество делителей четное

То есть у квадратов чисел корни натуральные числа?

@Gdez · 17.01.2021, 23:41

gray621, нет
4 -> 1, 2, 4
9 -> 1, 3, 9
16 -> 1, 2, 4, 8 16
и тд
Допустим 36 -> (1 и 36) + (2 и 18) + (3 и 12) + (4 и 9) + (6 и 6)... Но 6 и 6 это одно число. Итого четыре пары делителей плюс один делитель (для 36 это 6). Это для всех чисел, которые квадраты какого то натурального делителя.

Добавлено через 2 минуты
А вообще, задача без функций и списков некорректна. Когда найдешь код, который пройдет все тесты, попробуй число, допустим, 59 или 77

@gray621 · 18.01.2021, 00:14 **[ТС]**

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

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 15 секунд

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

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 10 секунд

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

Когда найдешь код, который пройдет все тесты

Твой код прошёл

Добавлено через 22 минуты
Зачем проверка для чётного кол-во делителей

Python
1
if int(number ** 0.5) != number ** 0.5:

И ещё почему в range + 1?

Python
1
range(1, int(number ** 0.5) + 1):

@Gdez · 18.01.2021, 04:38

gray621,

Зачем проверка для чётного кол-во делителей

Потому что для четных диапазон :

Python
1
range(1, int(number ** 0.5) + 1):

Для нечетных изначально можно не включать значение корня (для 36 число 6 уже входит -> count_of_dividers = 1)
Для четных нужно включать => допустим 42 -> его "целый" корень = 6 и для 6 парный делитель 7.
Если убрать проверку (что число не квадрат другого числа), то для N = 10 выведет ответ -> 36 -> посчитает пару (6 и 6)

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	17.01.2021, 20:42
	gray621, подсказка - количество делителей : $https://www.cyberforum.ru/cgi-bin/latex.cgi?\prod_{}^{}({{p}_{i}}^{} + 1)$ Где $https://www.cyberforum.ru/cgi-bin/latex.cgi?{p}_{i}$ - степень простого i-го множителя в составе исходного числа 24 -> 2223 -> $https://www.cyberforum.ru/cgi-bin/latex.cgi?{2}^{3} {3}^{1}$ Итого множителей = (3+1) * (1+1) = 8 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	17.01.2021, 21:06
	gray621, ограничения на "n" есть ? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	17.01.2021, 23:41
	gray621, нет 4 -> 1, 2, 4 9 -> 1, 3, 9 16 -> 1, 2, 4, 8 16 и тд Допустим 36 -> (1 и 36) + (2 и 18) + (3 и 12) + (4 и 9) + (6 и 6)... Но 6 и 6 это одно число. Итого четыре пары делителей плюс один делитель (для 36 это 6). Это для всех чисел, которые квадраты какого то натурального делителя. Добавлено через 2 минуты А вообще, задача без функций и списков некорректна. Когда найдешь код, который пройдет все тесты, попробуй число, допустим, 59 или 77 0

Найти число по количеству делителей

Решение