Игра факторизации

13

вход

Одно целое число 1≤x≤1015 .

Выход

Максимальное количество различных положительных целых чисел, которые имеют произведение x .

Примеры

Входные данные: 1099511627776. Выходные данные: 9. Один из возможных оптимальных списков факторов: (1, 2, 4, 8, 16, 32, 64, 128, 4096).

Входные данные: 127381. Выходные данные 4. Один из возможных оптимальных списков факторов: (1, 17, 59, 127).

Связанный с этим старым вопросом .

code-golf math Ануш
источник
9
Не могли бы вы добавить еще несколько тестов? (Желательно разумного размера.)
Арно
8
Учитывая ваши комментарии к большинству ответов: если вы ищете эффективный код, это не должно быть помечено как code-golf. Вы можете рассмотреть fastest-codeили fastest-algorithmдля предстоящего испытания. Если вы действительно хотите, чтобы все ответы работали в течение ограниченного времени в указанном диапазоне, это должно было быть явно упомянуто. (И я бы порекомендовал меньший диапазон, чтобы он code-golfполностью не конфликтовал .)
Арно
@Arnauld Нет, я осторожен, чтобы сделать это код-гольфом, и никто не осужден за это. Было бы здорово, если бы код мог работать для указанных диапазонов ввода.
Ануш
5
Цитата xnor: Если это не обязательно, ответы не сделают .
Арно
1
Ибо x=1, 2, ...я получаю то, f(x)=1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 3, 4, 2, 3чего не нахожу в OEIS. Достаточно ясно, что записи появятся для факторных чисел x. Например самый маленький xтакой, который f(x)=13будет 13!. Я думаю, fзависит только от показателей простой факторизации. Так что найти f(13^4*19^7*29^2)мы могли бы упростить до f(2^7*3^4*5^2).
Джепп Стиг Нильсен

Ответы:

5

Wolfram Language (Mathematica) , 52 байта

Max[Length/@Cases[Subsets@Divisors@#,{a__}/;1a==#]]&

Попробуйте онлайн!

4 байта сохранены благодаря @attinat

Вот также версия 153 байта, которая вычисляет 1099511627776и10^15 

Max[Length/@Table[s=RandomSample@Flatten[Table@@@FactorInteger[#]];Last@Select[Times@@@TakeList[s,#]&/@IntegerPartitions@Length@s,DuplicateFreeQ],5!]]+1&

Попробуйте онлайн!

Результат для 10^15является 12

{1, 2, 4, 5, 10, 16, 25, 40, 50, 100, 125, 250}

J42161217
источник
Вылетает с 1099511627776
Anush
7
@ Ануш Это не терпит крах. Просто нужна память. Вы ничего не сказали об ограничении памяти. Это код гольфа
J42161217
Да, я понимаю. Было бы неплохо, если бы вы могли на самом деле запустить код входных диапазонов, указанных в вопросе.
Ануш
6
@Anush Это код-гольф. Не хорошие ответы. Пожалуйста, укажите ваши критерии. Ответ либо действителен, либо нет. Я думаю, что проблема здесь заключается в вопросе ... Может быть, вы должны изменить его на "наиболее достаточный алгоритм"
J42161217
3
@Anush Я внес изменение в свой ответ и добавил еще одну версию, которая действительно быстра и эффективна на тот случай, если вы захотите это проверить
J42161217
3

05AB1E , 9 байт

Очень неэффективно. Тайм-аут на TIO для чисел с большим количеством делителей.

ÑæʒPQ}€gZ

Попробуйте онлайн!

объяснение

Ñ          # push a list of divisors of the input
 æ         # push the powerset of that list
  ʒPQ}     # filter, keep only the lists whose product is the input
      €g   # get the length of each
        Z  # take the maximum
Emigna
источник
Ваш код TIO, кажется, выводит 3 вместо 9.
Anush
@Anush: Это другое число, чем в вашем примере (так как это время из-за многих факторов). Я, вероятно, должен использовать более четкий пример.
Эминья
€gZнемного эффективнее, чем éθgдля того же bytecount.
Grimmy
@ Грими: Правда. Это не будет иметь большого значения, так как это фильтр, который является большим плохим парнем здесь, но это не мешает быть немного более эффективным :)
Emigna
2

Perl 6 , 38 байт

{$!=$_;+grep {$!%%$_&&($!/=$_)},1..$_}

Попробуйте онлайн!

Принимает жадный подход к выбору делителей.

Джо Кинг
источник
Не заканчивается с 1099511627776
Anush
6
@Anush Ну, это заканчивается в конце концов . Как правило, ответ действителен, если алгоритм программы будет работать с любым вводом, если ему будет предоставлено столько памяти и времени, сколько ему нужно. Поскольку это код-гольф , я оптимизировал его для длины кода, а не алгоритмической сложности
Джо Кинг,
2

Javascript (ES6), 39 байт

f=(n,i=0)=>n%++i?n>i&&f(n,i):1+f(n/i,i)

Там, вероятно, несколько байтов, которые могут быть сохранены здесь и там. Просто использует жадный алгоритм для факторов.

vrugtehagel
источник
2

Желе , 9 байт

ŒPP=³ƊƇẈṀ

Попробуйте онлайн!

-1 байт, спасибо кому-то

-2 байта благодаря ErikTheOutgolfer

HyperNeutrino
источник
При подготовке ввода для superseeker OEIS, я создал 11-байтовое вероятно golfable программы Желе (который использует другой подход), и я вряд ли отправить ответ Желе , так что я сделаю вид , что golfed байт из вашего решения: ÆE×8‘½’:2S‘(это работает с мощностью раздела «формула» OEIS для A003056). Отказ от ответственности: это может быть неправильно, но это работает на тестовых случаях.
мое местоимение monicareinstate
Кажется, он не заканчивается 1099511627776
Anush
@ someone не работает на 36, но спасибо
HyperNeutrino
@ Ануш, да, это действительно медленно, потому что я играю в гольф, а не оптимизирован для эффективности
HyperNeutrino
1
Вы можете удалить ÆD, это не значит, что будет создано больше разделов, как это, просто это займет гораздо больше времениИкс≥21).
Эрик Outgolfer
2

Брахилог , 8 байт

f;?⟨⊇×⟩l

Попробуйте онлайн!

(Наивный подход, {~×≠l}ᶠ⌉ генерирует бесконечное количество решений с дополнительными единицами, прежде чем удалять их ≠, и, таким образом, фактически не завершается. Однако это не проблема, поскольку он для того же количества байтов!)

Принимает ввод через входную переменную и выводит через выходную переменную. Заголовок на TIO содержит копию большей части кода, чтобы показать вам, что такое список факторов, но без него это прекрасно работает. Поскольку ⊇сначала создаются большие подсписки, этот предикат, по сути, делает то же самое, что и большинство других ответов, но без явного генерирования и фильтрации полного набора мощностей факторов благодаря обратной проверке.

            The output
       l    is the length of
    ⊇       a sublist (the largest satisfying these constraints)
f           of the factors of
            the input
 ; ⟨  ⟩     which
     ×      with its elements multiplied together
  ?         is the input.
Несвязанная строка
источник
1

Gaia , 10 9 байт

Π=
dz↑⁇(l

Попробуйте онлайн!

Следует тому же «алгоритму», что и в другом месте - отфильтруйте набор мощности делителя для самого длинного с произведением, равным числу, и верните его длину.

	| helper function
Π=	| is prod(list)==n (implicit)?
	|
	| main function; implicitly takes n
dz	| divisor powerset (in decreasing order of size)
  ↑⁇	| filter by helper function
    (l	| take the first element and take the length (implicitly output)
Giuseppe
источник
0

Моллюск , 15 байт

p}_`nq#:;qQ@s~Q

Ссылка TIO скоро появится (когда Деннис тянет)

В основном это порт решения @ Emigna 05AB1E.

объяснение

                - Implicit Q = first input
p               - Print...
 }              - The last element of...
  _             - Sorted...
   `nq          - Lengths of... (map q => q.len)
           @s   - Items in powerset of
             ~Q - Proper divisors of Q
      #         - Where... (filter)
        ;q      - Product of subset
       :        - Equals...
          Q     - Q
Skidsdev
источник
0

C # (интерактивный компилятор Visual C #) , 54 байта

int f(int n,int i=0)=>n%++i<1?1+f(n/i,i):n>i?f(n,i):0;

Использует тот же подход, что и ответы @ vrugtehagel и @ JoKing.

Попробуйте онлайн!

Воплощение невежества
источник
При условии, что я правильно реализовал вашу логику, 53-байтовое решение (от которого я не смог избавиться от ключевого слова return): попробуйте онлайн!
мое местоимение monicareinstate
1
@ Someone Спасибо, но согласно мета, функции должны быть многоразовыми . Кроме того, я не знаю, допустимо ли, чтобы объявления вне функции пропускали конечную точку с запятой, может сделать мета-пост по этому вопросу.
Воплощение неведения
0

Рубин , 34 байта

Очевидно, тайм-аут этого огромного числа, но в конечном итоге истечет, если будет достаточно времени на другой машине.

->n{(1..n).count{|e|n%e<1?n/=e:p}}

Попробуйте онлайн!

Значение чернил
источник