Найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N

@Gerasick · Регистрация: 15.11.2023

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

Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.

Входные данные
В единственной строке входного файла INPUT.TXT записано одно целое число N (0 ≤ N ≤ 10⁹).

Выходные данные
В выходной файл OUTPUT.TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

Примеры:
10 25
13 -1
8 8
90 259

Прошу писать программу как можно более простой и понятной, спасибо

@thyrex · 23.11.2023, 22:14

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
if n == 0:
    print(10)
elif 1<=n<=9:
    print(n)
else:
    d = [0]*10
    for i in range(9, 1, -1):
        while n%i == 0:
            d[i] += 1
            n //= i
    if n != 1:
        print(-1)
    else:
        for i in range(2, 10):
            for k in range(1, d[i]+1):
                print(i, end = '')

@idealist · 23.11.2023, 23:59

Ну или так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def get_num(n):
    if not n:
        return 10
    if n == 1:
        return 1
    s = ''
    for i in range(9,2-1,-1):
        while n%i == 0:
            s = str(i) + s
            n //= i
            if n == 1:
                return int(s)
    return -1
 
n = int(input('n = '))
print(get_num(n))

@afors · 24.11.2023, 17:58

Может не самый быстрый способ, но как вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def res(n, max = 1000000):
    for i in range(1, max+1):
        rslt = ''
        valstr = str(i)
        for j in valstr:
            rslt += j
        r = 1
        for k in rslt:
            r = r * int(k)
        if r == n:
            return(rslt)
    return(-1)
 
 
print(res(729, 1000000)) # Вывод 999

@idealist · 24.11.2023, 18:23

afors, что-то у вас неправильно считает. Для миллиона есть решение, а у вас нет.

@afors · 24.11.2023, 19:23

idealist, Решение для миллиона 55555588. Просто в функции надо увеличить значение max (max >= 55555588). Считает, но очень долго. Алгоритм не эффективен, согласен!

@idealist · 24.11.2023, 21:08

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

Алгоритм не эффективен, согласен

А что за алгоритм?

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@Gerasick 11 / 10 / 1 Регистрация: 15.11.2023 Сообщений: 55

	Найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N 23.11.2023, 21:47. Показов 2393. Ответов 6 Метки нет (Все метки) Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N. Входные данные В единственной строке входного файла INPUT.TXT записано одно целое число N (0 ≤ N ≤ 10⁹). Выходные данные В выходной файл OUTPUT.TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1. Примеры: 10 25 13 -1 8 8 90 259 Прошу писать программу как можно более простой и понятной, спасибо 0

@idealist 3750 / 1944 / 613 Регистрация: 21.11.2021 Сообщений: 3,706
	24.11.2023, 18:23
	afors, что-то у вас неправильно считает. Для миллиона есть решение, а у вас нет. 0

@afors 0 / 0 / 0 Регистрация: 24.11.2023 Сообщений: 2
	24.11.2023, 19:23
	idealist, Решение для миллиона 55555588. Просто в функции надо увеличить значение max (max >= 55555588). Считает, но очень долго. Алгоритм не эффективен, согласен! 0

Опции темы