Максимальная взаимно-простая факторизация

14

Определения

  • Два числа взаимно просты, если их единственный положительный общий делитель равен 1.
  • Список чисел взаимно прост, если каждая пара чисел в этом списке взаимно проста.
  • Факторизация числа n- это список чисел, произведением которых является n.

задача

Учитывая положительное число n, выведите взаимно взаимно простое разложение nс максимальной длиной, которая не включает 1.

пример

Ибо n=60ответ таков [3,4,5], потому что 3*4*5=60никакая другая взаимно простая первичная факторизация не 1имеет длины, большей или равной 3длине факторизации.

Правила и свободы

  • Вы можете использовать любой разумный формат ввода / вывода.
  • Записи в списке вывода не нужно сортировать.

Testcases

n   output
1   []
2   [2]
3   [3]
4   [4]
5   [5]
6   [2, 3]
7   [7]
8   [8]
9   [9]
10  [2, 5]
11  [11]
12  [3, 4]
13  [13]
14  [2, 7]
15  [3, 5]
16  [16]
17  [17]
18  [2, 9]
19  [19]
20  [4, 5]
21  [3, 7]
22  [2, 11]
23  [23]
24  [3, 8]
25  [25]
26  [2, 13]
27  [27]
28  [4, 7]
29  [29]
30  [2, 3, 5]
31  [31]
32  [32]
33  [3, 11]
34  [2, 17]
35  [5, 7]
36  [4, 9]
37  [37]
38  [2, 19]
39  [3, 13]
40  [5, 8]
41  [41]
42  [2, 3, 7]
43  [43]
44  [4, 11]
45  [5, 9]
46  [2, 23]
47  [47]
48  [3, 16]
49  [49]
50  [2, 25]
51  [3, 17]
52  [4, 13]
53  [53]
54  [2, 27]
55  [5, 11]
56  [7, 8]
57  [3, 19]
58  [2, 29]
59  [59]
60  [3, 4, 5]
61  [61]
62  [2, 31]
63  [7, 9]
64  [64]
65  [5, 13]
66  [2, 3, 11]
67  [67]
68  [4, 17]
69  [3, 23]
70  [2, 5, 7]
71  [71]
72  [8, 9]
73  [73]
74  [2, 37]
75  [3, 25]
76  [4, 19]
77  [7, 11]
78  [2, 3, 13]
79  [79]
80  [5, 16]
81  [81]
82  [2, 41]
83  [83]
84  [3, 4, 7]
85  [5, 17]
86  [2, 43]
87  [3, 29]
88  [8, 11]
89  [89]
90  [2, 5, 9]
91  [7, 13]
92  [4, 23]
93  [3, 31]
94  [2, 47]
95  [5, 19]
96  [3, 32]
97  [97]
98  [2, 49]
99  [9, 11]

счет

Это . Кратчайший ответ в байтах побеждает.

Дрянная Монахиня
источник
OEIS для длины вывода.
Мартин Эндер
OEIS для сплющенной последовательности. (С ведущим 1.)
Мартин Эндер
Более сложная последующая задача: только смежные пары в результирующем списке должны быть взаимно простыми.
Мартин Эндер
4
Это просто разложение на основные силы?
Paŭlo Ebermann
1
@ PaŭloEbermann да, это так.
Утренняя монахиня

Ответы:

10

Математика , 24 байта

#^#2&@@@FactorInteger@#&

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

Мартин Эндер
источник
5
#^#2&@@@FactorInteger@#&[1]возвращается {1}в Mathematica. Но это работает в математике.
алефальфа
@alephalpha Спасибо, мне даже не пришло бы в голову посмотреть, как Mathics реализует по- FactorIntegerдругому. :)
Мартин Эндер
9

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

ḋḅ×ᵐ

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

объяснение

       # output is the list of
  ×ᵐ   # products of each
 ḅ     # block of consecutive equal elements
ḋ      # of the prime factors
       # of the input
Emigna
источник
2
Поздравляю с первым ответом на брахилоге! ... по крайней мере, я думаю?
фатализировать
1
@Fatalize: мой второй, я думаю. У меня был этот раньше. Определенно мой самый короткий, хотя :)
Emigna
5

05AB1E , 3 5 байт

+2 байта, чтобы исправить крайний случай 1. Спасибо Райли за патч (и за набор тестов, мой 05ab1e не такой сильный!)

ÒγP1K

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

Как?

Ò     - prime factorisation, with duplicates
 γ    - split into chunks of consecutive equal elements
  P   - product of each list
   1  - literal one
    K - removed instances of top from previous
      - implicitly display top of stack
Джонатан Аллан
источник
@Adnan - это лучшая ссылка для "байтов" или где-то есть отформатированная кодовая страница?
Джонатан Аллан
Да, есть кодовая страница, которая отображает все байты.
Аднан,
1
О, как я это пропустил> _ <Большое спасибо :)
Джонатан Аллан
Не работает для 1.
Утренняя монахиня
@LeakyNun исправился с помощью :)
Джонатан Аллан
3

CJam , 9 байт

{mF::#1-}

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

Просто разделяет входные данные на составляющие его простые степени и удаляет 1s (необходимо только для ввода 1).

Мартин Эндер
источник
3

Haskell , 51 байт

(2#) является анонимной функцией, которая принимает целое число и возвращает список

Используйте как (2#) 99.

m#n|m>n=[]|x<-gcd(m^n)n=[x|x>1]++(m+1)#div n x
(2#)

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

Вдохновленные уловкой власти, некоторые люди использовали в недавней проблеме числа без квадратов .

  • m#nгенерирует факторы n, начиная с m.
  • Если m>nмы остановимся, заключив, что мы уже нашли все факторы.
  • x=gcd(m^n)nявляется крупнейшим фактором, nчьи главные факторы все в m. Обратите внимание, что, поскольку меньшие mтестируются в первую очередь, это будет, 1если не mявляется простым.
  • Мы включаем xв итоговый список, если это не 1, и затем повторяем с последующим mделением nна x. Обратите внимание , что xи div n xне могут иметь общие факторы.
  • (2#)берет число и начинает находить его факторы 2.
Орджан Йохансен
источник
3

MATL , 7 байт

&YF^1X-

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Рассмотрим ввод 80 в качестве примера.

&YF    % Implicit input. Push array of unique prime factors and array of exponents
       % STACK: [2 3 5], [4 0 1]
^      % Power, element-wise
       % STACK: [16 1 5]
1      % Push 1
       % STACK: [16 1 5], 1
X-     % Set difference, keeping order. Implicitly display
       % STACK: [16 5]

РЕДАКТИРОВАТЬ (9 июня 2017 г.): YFв выпуске 20.1.0 были изменены два выхода : нефакторные простые числа и их (нулевые) показатели пропущены. Это не влияет на приведенный выше код, который работает без каких-либо изменений (но 1X-может быть удален).

Луис Мендо
источник
Я полагаю, что изменение означает, 1X-что в новом выпуске избыточно ... также, это выглядит как разность наборов, а не пересечение для меня.
Орджан Йохансен
@ ØrjanJohansen Правильно на обоих. Благодарность!
Луис Мендо
2

Желе , 5 байт

ÆF*/€

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

Как?

ÆF*/€ - Main link: n
ÆF    - prime factors as [prime, exponent] pairs
   /€ - reduce €ach with:
  *   - exponentiation
Джонатан Аллан
источник
Альтернативное решение 6-байтовое в попытке найти другой метод , который бы связать с вашими ( к сожалению , не суметь) ÆfŒgZP. У него такое же количество токенов, но слишком много двухбайтовых атомов;)
HyperNeutrino
... и, как и моя удаленная запись 05ab1e, она возвращает 1для ввода, 1который запрещен (эффект выполнения пустого продукта).
Джонатан Аллан
:( Ну что ж, упустил это из виду.
Черт
2

Алиса , 10 байт

Ifw.n$@EOK

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

К сожалению, здесь снова используются кодовые точки в качестве целочисленного ввода / вывода . Тестовый случай в ссылке TIO - это ввод 191808, который разбивается на 64 , 81 и 37 . Обратите внимание, что это решение печатает простые степени в порядке от наибольшего к наименьшему простому, поэтому мы получаем вывод %Q@.

Для удобства вот 16-байтовое решение с десятичным вводом / выводом, которое использует тот же алгоритм ядра:

/O/\K
\i>fw.n$@E

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

объяснение

Как и другие ответы, это разбивает входные данные на простые силы.

I      Read a code point as input.
f      Compute its prime factorisation a prime/exponent pairs and push them
       to the stack in order from smallest to largest prime.
w      Remember the current IP position on the return address stack. This
       starts a loop.
  .      Duplicate the current exponent. This will be zero once all primes
         have been processed.
  n$@    Terminate the program if this was zero.
  E      Raise the prime to its corresponding power.
  O      Output the result as a character.
K      Return to the w to run the next loop iteration.
Мартин Эндер
источник
2

Mathematica 46 байтов

#[[1]]^#[[2]]&/@If[#==1,#={},FactorInteger@#]&

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

J42161217
источник
Хороший ответ, но он дает немного неправильный вывод для некоторых тестовых случаев. В настоящее время ваш код {}; {2}; {3}; {2}; {5}; {2,3}; {7}; {2}; {3}; {2,5}; {11}; {2,3}; {13}; ... выводится, но {}; {2}; {3}; {4}; {5}; {2,3}; {7}; {8}; {9}; {2,5}; {11}; {4,3}; {13}; ...вместо этого он должен выводить .
Кевин Круйссен
Я думаю, что я это исправил
J42161217
Кажется, действительно работает в TIO . +1 О, и добро пожаловать в PPCG, я вижу, вы довольно новичок здесь. Вы, наверное, уже видели это, но если нет, то Советы по игре в гольф в Mathematica могут быть интересными для чтения. Приятного пребывания! :)
Кевин Круйссен
1
Если вы обнаруживаете, что обращаетесь к компонентам #больше, чем к #себе, вы можете сэкономить много байтов, используя Apply( @@@) вместо Map( /@):#^#2&@@@If...
Мартин Эндер
1

PHP, 62 байта

печатает ассоциативный массив с основным в качестве ключа и частотой использования простого в качестве значения и ничего для ввода 1

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!++$r[$i];print_r($r);

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

Выход для 60

Array
(
    [2] => 2
    [3] => 1
    [5] => 1
)

PHP, 82 байта

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);print_r($r);

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

ничего не печатает для ввода, 1если вы хотите вместо него пустой массив, а отсортированный массив будет немного длиннее

for($r=[],$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);sort($r);print_r($r);
Йорг Хюльсерманн
источник
0

miniML , 47 байт

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

fun n->map(fun p->ipow(fst p)(snd p))(factor n)

Обратите внимание, что «мини» в miniml относится к размеру набора функций, а не к размеру исходного кода, написанного на нем.

feersum
источник
0

Рубин, 61 байт

require 'prime'
->n{(2..n).select{|e|n/e.to_f%1==0&&e.prime?}}

Я очень разочарован после просмотра 6-7 байтных решений -))

marmeladze
источник
0

Mathematica, 24 байта

Power@@@FactorInteger@#&

Жаль, @@@*это не вещь. Кроме того , я хотел бы /@*, @@*и в самом деле, изменения @@@в /@@, //@к @@@или что - то и добавить бесконечное семейство из //@, ///@...

CalculatorFeline
источник