Maksymalne wzajemne rozkładanie na czynniki pierwsze

14

Definicje

  • Dwie liczby są współrzędne pierwsze, jeśli ich jedynym dodatnim wspólnym dzielnikiem jest 1.
  • Lista liczb jest wzajemnie pierwotna, jeżeli każda para liczb na tej liście jest wzajemnie pierwotna .
  • Faktoryzacja liczby nto lista liczb, których produktem jest n.

Zadanie

Biorąc pod uwagę liczbę dodatnią n, wyprowadzaj wzajemnie rozkład na czynniki pierwsze nz maksymalną długością, która nie obejmuje 1.

Przykład

Ponieważ n=60odpowiedź brzmi [3,4,5], ponieważ 3*4*5=60żadna inna wzajemnie pierwotna faktoryzacja bez nie 1ma długości większej lub równej 3długości faktoryzacji.

Zasady i wolności

  • Możesz użyć dowolnego rozsądnego formatu wejścia / wyjścia.
  • Wpisy na liście wyników nie muszą być sortowane.

Przypadki testowe

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]

Punktacja

To jest . Najkrótsza odpowiedź w bajtach wygrywa.

Leaky Nun
źródło
OEIS dla spłaszczonej sekwencji. (Z prowadzącym 1.)
Martin Ender
Trudniejsze wyzwanie kontrolne: tylko sąsiednie pary z wynikowej listy muszą być pierwszymi.
Martin Ender
4
Czy to tylko podział na moce główne?
Paŭlo Ebermann
1
@ PaŭloEbermann tak, jest.
Leaky Nun

Odpowiedzi:

10

Matematyka , 24 bajty

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

Wypróbuj online!

Martin Ender
źródło
5
#^#2&@@@FactorInteger@#&[1]powraca {1}w Mathematica. Ale działa w matematyce.
alephalpha
@alephalpha Dzięki, nawet nie przyszło mi do głowy, aby zobaczyć, czy matematyka implementuje FactorIntegerinaczej. :)
Martin Ender
9

Brachylog , 4 bajty

ḋḅ×ᵐ

Wypróbuj online!

Wyjaśnienie

       # output is the list of
  ×ᵐ   # products of each
 ḅ     # block of consecutive equal elements
ḋ      # of the prime factors
       # of the input
Emigna
źródło
2
Gratulujemy pierwszej odpowiedzi Brachylog! ... przynajmniej tak mi się wydaje?
Fatalize
1
@Fatalize: My 2nd Myślę, że. Miałem ten wcześniej. Zdecydowanie moja najkrótsza :)
Emigna
5

05AB1E , 3 5 bajtów

+2 bajty, aby naprawić wielkość krawędzi 1. Dzięki Riley za łatkę (i pakiet testowy mój 05ab1e nie jest aż tak silny!)

ÒγP1K

Pakiet testowy w Wypróbuj online!

W jaki sposób?

Ò     - 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
Jonathan Allan
źródło
@Adnan to najlepszy link do „bajtów”, czy też jest gdzieś sformatowana strona kodowa?
Jonathan Allan
Tak, istnieje strona kodowa wyświetlająca wszystkie bajty.
Adnan
1
Och, jak mi tego brakowało> _ <Dziękuję bardzo :)
Jonathan Allan
Nie działa dla 1.
Leaky Nun
@LeakyNun naprawił się z pomocą :)
Jonathan Allan
3

CJam , 9 bajtów

{mF::#1-}

Wypróbuj online!

Po prostu dzieli dane wejściowe na podstawowe składowe mocy i usuwa 1s (konieczne tylko dla danych wejściowych 1).

Martin Ender
źródło
3

Haskell , 51 bajtów

(2#) to anonimowa funkcja przyjmująca liczbę całkowitą i zwracająca listę.

Użyj jako (2#) 99.

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

Wypróbuj online!

Zainspirowany sztuczką mocy, którą niektórzy wykorzystali w ostatnim konkursie liczbowym bez kwadratów .

  • m#ngeneruje czynniki n, zaczynając od m.
  • Jeśli m>nprzestaniemy, stwierdzając, że znaleźliśmy już wszystkie czynniki.
  • x=gcd(m^n)njest największym czynnikiem, w nktórym wszystkie czynniki pierwsze są m. Zauważ, że ponieważ mniejsze msą najpierw testowane, będzie to możliwe, 1chyba że mjest liczbą pierwszą.
  • Uwzględniamy xna wynikowej liście, jeśli nie jest to 1, a następnie powtarzamy z następną m, dzieląc nprzez x. Pamiętaj, że xi div n xnie mogą mieć wspólnych czynników.
  • (2#)bierze liczbę i zaczyna szukać jej czynników 2.
Ørjan Johansen
źródło
3

MATL , 7 bajtów

&YF^1X-

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Rozważ dane wejściowe 80 jako przykład.

&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]

EDYCJA (9 czerwca 2017 r.): YFDwie wersje zostały zmodyfikowane w wersji 20.1.0 : liczby pierwsze nieczynnikowe i ich (zero) wykładniki są pomijane. Nie wpływa to na powyższy kod, który działa bez żadnych zmian (ale 1X-można go usunąć).

Luis Mendo
źródło
Zakładam, że środek zmiany 1X-jest zbędny w nowym wydaniu ... także, że dla mnie wygląda to raczej na różnicę, niż na skrzyżowanie.
Ørjan Johansen
@ ØrjanJohansen Poprawnie w obu przypadkach. Dzięki!
Luis Mendo,
2

Galaretka , 5 bajtów

ÆF*/€

Pakiet testowy w Wypróbuj online!

W jaki sposób?

ÆF*/€ - Main link: n
ÆF    - prime factors as [prime, exponent] pairs
   /€ - reduce €ach with:
  *   - exponentiation
Jonathan Allan
źródło
Alternatywnym rozwiązaniem 6 bajtów, próbując znaleźć inny sposób, który będzie związać z naszą (niestety braku) ÆfŒgZP. Ma taką samą liczbę tokenów, ale zbyt wiele dwubajtowych atomów;)
HyperNeutrino
... i podobnie jak mój usunięty wpis 05ab1e zwraca wartość, 1której wejście 1jest niedozwolone (efekt wykonania pustego produktu).
Jonathan Allan
:( Ups, przeoczyłem to. Darn.: P
HyperNeutrino
2

Alice , 10 bajtów

Ifw.n$@EOK

Wypróbuj online!

Niestety, ponownie używa punktów kodowych jako liczb całkowitych we / wy . Przypadek testowy w łączu TIO to wejście 191808, które rozkłada się na 64 , 81 i 37 . Zauważ, że to rozwiązanie drukuje moce główne w kolejności od największej do najmniejszej liczby pierwszej, więc otrzymujemy wynik %Q@.

Dla wygody oto 16-bajtowe rozwiązanie z dziesiętnym We / Wy, które wykorzystuje ten sam algorytm podstawowy:

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

Wypróbuj online!

Wyjaśnienie

Podobnie jak inne odpowiedzi, rozkłada to dane wejściowe na moce główne.

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.
Martin Ender
źródło
2

matematyka 46 bajtów

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

Wypróbuj online!

J42161217
źródło
Dobra odpowiedź, ale daje nieco niepoprawne dane wyjściowe dla niektórych przypadków testowych. Obecnie Twój kod wyjściowy, {}; {2}; {3}; {2}; {5}; {2,3}; {7}; {2}; {3}; {2,5}; {11}; {2,3}; {13}; ... ale powinien {}; {2}; {3}; {4}; {5}; {2,3}; {7}; {8}; {9}; {2,5}; {11}; {4,3}; {13}; ...zamiast tego.
Kevin Cruijssen
Myślę, że to naprawiłem
J42161217
Wygląda na to, że rzeczywiście działa w TIO . +1 Och, i witam w PPCG, widzę, że jesteś tu całkiem nowy. Prawdopodobnie już to widziałeś, ale jeśli nie, Porady dotyczące gry w golfa w Mathematica mogą być interesujące do przeczytania. Miłego pobytu! :)
Kevin Cruijssen
1
Jeśli uzyskasz dostęp do komponentów #więcej niż on #sam, możesz zaoszczędzić wiele bajtów, używając Apply( @@@) zamiast Map( /@):#^#2&@@@If...
Martin Ender
1

PHP, 62 bajty

wypisuje tablicę asocjacyjną z liczbą pierwszą jako kluczem i jak często liczba pierwsza jest używana jako wartość i nic do wprowadzania 1

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

Wypróbuj online!

Wyjście dla 60

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

PHP, 82 bajty

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

Wypróbuj online!

nic nie wypisuje na wejściu, 1jeśli wolisz pustą tablicę, a posortowana tablica będzie trochę dłużej

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);
Jörg Hülsermann
źródło
1

Właściwie 6 bajtów

w⌠iⁿ⌡M

Wypróbuj online!

Wyjaśnienie:

w⌠iⁿ⌡M
w       factor into [prime, exponent] pairs
 ⌠iⁿ⌡M  for each pair:
  i       flatten
   ⁿ      prime**exponent
Mego
źródło
0

miniML , 47 bajtów

Wyzwania dotyczące faktoryzacji pierwszorzędnej są tutaj straszliwie nadmiernie reprezentowane, dlatego wszyscy jesteśmy niestety zmuszeni do faktoryzacji w standardowej bibliotece.

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

Zauważ, że „mini” w miniml odnosi się do rozmiaru zestawu funkcji, a nie do rozmiaru kodu źródłowego w nim zapisanego.

feersum
źródło
0

Rubin, 61 bajtów

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

Jestem naprawdę rozczarowany szukaniem rozwiązań 6-7-bajtowych -))

marmeladze
źródło
0

Mathematica, 24 bajty

Power@@@FactorInteger@#&

Szkoda @@@*nie jest rzeczą. Również chciałbym /@*, @@*iw rzeczywistości, zmiana @@@celu /@@, //@do @@@lub cokolwiek i dodać nieskończoną rodziny //@, ///@...

CalculatorFeline
źródło