Коллекция положительных целых чисел d_1 d_2 ... d_k
является факторизацией положительного целого числа, n
если
d_1 * d_2 * ... * d_k = n
Каждое положительное целое число имеет уникальную первичную факторизацию , но в целом они также имеют факторизации, в которых некоторые термины являются составными. Например
12 = 6 * 2 = 4 * 3 = 3 * 2 * 2
Напишите программу, функцию, глагол или тому подобное, который принимает в качестве входных данных одно положительное целое число и возвращает или печатает полный список его отдельных факторизаций. Факторизации могут быть произведены в любом порядке, и их условия могут быть в любом порядке, но никакие два не должны быть перестановками друг друга. Факторизация может не включать 1
два исключения: для ввода n
вы можете указать факторизацию n*1
вместо n
; и для ввода 1
вы можете 1
указать факторизацию вместо пустого списка.
Вы можете предположить, что входные данные будут находиться в диапазоне 32-разрядного целого числа со знаком. Если выходные данные представлены в виде строки, должно быть четкое разграничение между разграничением чисел в разложении и разграничением разложений, но нет необходимости (например), чтобы факторы соединялись с *
.
Ваш код должен быть в состоянии обработать любой допустимый ввод в течение 10 минут на приемлемом настольном компьютере.
Примеры
1 [[]]
or [[1]]
or [[1 1]]
7 [[7]]
or [[7 1]]
or [[1 7]]
12 [[12] [6 2] [4 3] [2 3 2]]
or variants
16 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
or variants
901800900 a list of 198091 factorisations
1338557220 a list of 246218 factorisations
источник
901800900
и1338557220
где-нибудь, где мы можем их проверить? Мой код дает мне 2048 и 1024 факторизации для этих чисел соответственно, и я не уверен почему.Ответы:
Haskell, 56 байт
(2!)(1338557220::Int)
печатает через пять минут на моем ноутбуке, когда скомпилировано сghc -O3
.Haskell, 62 байта, но намного быстрее
(2!)(1338557220::Int)
печатается за четверть секунды на моем ноутбуке при компиляции сghc -O3
.источник
ghc
дает мнеParse error: naked expression at top level
иghci
дает мнеparse error on input `='
(2!)
программойmain = print ((2!) (1338557220::Int))
, скомпилироватьghc -O3 factor.hs
и запустить с помощью./factor
.Pyth, 29 байт
Попробуйте онлайн
Работает за двадцать секунд
1338557220
на моем ноутбуке.источник
pyth factor.pyth
(илиpyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'
) предоставление16
на stdin. Убедитесь, что вы используете текущую версию Pyth; неявныйQ
был добавлен в марте. Я не могу представить, как вы можете получить деление на ноль, хотя."
вместо'
, а bash расширял что-!%
то еще.Python ,
2523133123111451411371351038483 байтаЭто в значительной степени основано на ответе Питера Андерса Касерга . Любые предложения по игре в гольф приветствуются. Попробуйте онлайн!
Редактировать: 19 байтов в гольф благодаря Деннису. Исправлена опечатка в коде и добавлена ссылка TIO.
Ungolfed:
источник
**.5
избавляется от импорта.JavaScript (ES6), 83 байта
Только заимствовал уловку квадратного корня @ AndersKaseorg, потому что в итоге я сэкономил байты. Печатает
1
для ввода1
, в противном случае не печатает1
s.источник
Ruby 1,9+,
878987 байтЭтот ответ основан на ответе Питера Андерса Касерга . Этот код работает только для версий после Ruby 1.9, так как стабильные лямбды
->
были введены только в 1.9. Любые предложения по игре в гольф приветствуются.Ungolfed:
источник
g[n/d,d]
:wrong number of arguments (0 for 1)
->
в Ruby 1.9 были введены стабильные лямбды . Я отредактирую ответ, чтобы показать требуемый номер версии.g[n/d,d]
.g(n/d,d)
является более обратно-совместимым.f[n]
это требуется для вызова стабильных лямбд и руби лямбд в целом.f(n)
иf n
звонки требуютdef
иend
. Больше информации здесь и здесьJ, 52 байта
Не так эффективно, как могло бы быть, поскольку некоторые факторизации могут повторяться, и последний этап должен быть сделан после сортировки каждой факторизации и затем дедупликации.
Попробуйте онлайн! (Но старайтесь, чтобы входные значения были небольшими).
На моем рабочем столе время
объяснение
Этот метод основан на генерации всех установленных разделов для простых множителей входного целого числа n . Производительность наилучшая, когда n не содержит квадратов, в противном случае будут созданы повторяющиеся факторизации.
источник