Uwaga: to wyzwanie zostało opublikowane w piaskownicy .

Wprowadzenie

Wyzwanie to jest inspirowane przez 2009 Putnam B1 , problem w konkursie matematyki na studiach licencjackich. Problem jest następujący:

Pokaż, że każdą dodatnią liczbę wymierną można zapisać jako iloraz iloczynów silni (niekoniecznie odrębnych) liczb pierwszych. Na przykład,

Wyzwanie

Wyzwanie polega na przyjęciu pary względnie pierwszych liczb całkowitych dodatnich reprezentujących licznik i mianownik dodatniej liczby wymiernej (lub po prostu samej liczby wymiernej) jako danych wejściowych i wyprowadzenie dwóch list (lub tablic itp.) Liczb pierwszych, tak aby wprowadzona liczba wymierna jest równa stosunkowi iloczynu silni liczb pierwszych z pierwszej listy do iloczynu silni liczb pierwszych z drugiej listy.

Notatki

• Może nie być żadnych liczb pierwszych, które zawierałyby zarówno na pierwszej liście, jak i na drugiej liście; liczba pierwsza może jednak pojawiać się tyle razy, ile zechce się na każdej liście.
• Można przyjąć, że dane wejściowe wynoszą (bez ograniczeń) między 1 a 65535; nie można jednak założyć, że silnia liczb, które trzeba wyprowadzić, będzie w tym zakresie.

Przykład wejścia i wyjścia

Oto przykłady legalnych danych wejściowych i wyjściowych.

input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5]     (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]

Dane wejściowe (2,2), (0,3), (3,0), (3,6) i (1 65536) są nielegalnymi danymi wejściowymi (tzn. Twój program nie musi zachowywać się w żaden szczególny sposób na nich ). Oto kilka przykładów nielegalnych wyników:

1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)

Punktacja

To jest golf golfowy , więc wygrywa najniższy wynik w bajtach!

05AB1E , 54 53 48 46 40 35 33 32 28 bajtów

[D¿÷Z#DÓ€gZD<ØŠQ*DˆR!*]¯øεʒĀ

Wypróbuj online! Edycja: Zapisano 2 bajty dzięki tylko @ ASCII. Zaoszczędź 1 2 3 4 bajty dzięki @Emigna. (Muszę uratować jeszcze tylko jeden i jestem o połowę mniejszy od oryginalnej liczby bajtów!) Objaśnienie:

[       Begin an infinite loop
D¿÷     Reduce to lowest terms
Z#      Exit the loop if the (largest) value is 1
DÓ€g    Find the index of the largest prime factor of each value
Z       Take the maximum
D<ØŠ    Convert index back to prime and save for later
Q       Convert to an pair of which value had the largest prime factor
*       Convert to an pair with that prime factor and zero
Dˆ      Save the pair in the global array for later
R!*     Multiply the other input value by the factorial of the prime
]       End of infinite loop
¯ø      Collect all the saved primes
εʒĀ     Forget all the saved 0s

Mathematica, 175 177 169 154 108 bajtów

Join@@@Table[x[[1]],{s,{1,-1}},{x,r@#},x[[2]]s]&@*(If[#==1,1,{p,e}=Last@(r=FactorInteger)@#;p^e#0[p!^-e#]]&)

Wypróbuj online!

Jak to działa

Jest to kompozycja dwóch funkcji. Pierwszy, który nie lubi

If[# == 1,
  1,
  {p,e} = Last[FactorInteger[#]];
  p^e * #0[p!^-e * #]
]&

jest funkcją rekurencyjną do faktycznego obliczania pożądanej faktoryzacji. Konkretnie, biorąc pod uwagę racjonalne dane wejściowe x, obliczamy liczby pierwsze, których silnia powinna znajdować się w liczniku i mianowniku, i zwracamy ułamek wraz ze wszystkimi tymi liczbami pierwotnymi pomnożonymi razem. (Na przykład 10/9 = 2!*5!/(3!*3!*3!)wracamy 10/27 = 2*5/(3*3*3)).

Robimy to, radząc sobie z największym czynnikiem pierwszym na każdym etapie: jeśli p ^e występuje w rozkładzie x, upewniamy się, że p! ^e występuje w rozkładzie na czynniki i powtarza się na x podzielone przez p! ^e .

(Wcześniej miałem bardziej sprytną strategię, która pozwala uniknąć dużych liczb, patrząc na poprzednią liczbę pierwszą przed p, ale Mathematica może łatwo obsługiwać liczby tak duże jak 65521 !, więc nie ma sensu. Stara wersja, którą można znaleźć w historii, to znacznie szybciej: na moim komputerze zajęło to 0,05 sekundy na wejściach obsługiwanych przez tę wersję w 1,6 sekundy.)

Druga funkcja zamienia wynik pierwszej funkcji w listy liczb pierwszych.

Join @@@ 
  Table[x[[1]],
    {s,{1,-1}},
    {x,FactorInteger[#]},
    x[[2]]*s
  ]&

Dla s=1(mocy dodatnich) i s=-1(mocy ujemnych) oraz dla każdego terminu {prime,exponent}w rozkładzie na czynniki r@#powtarzamy liczbę pierwszą prime exponent*swiele razy.

Wersja niekonkurencyjna z 109 62 bajtami

If[#==1,∇1=1,{p,e}=Last@FactorInteger@#;(∇p)^e#0[p!^-e#]]&

To samo co powyżej, ale zamiast dać wynik jako listę, daje wynik jako wyrażenie, używając operatora ∇ (ponieważ nie ma wbudowanego znaczenia) jako stand-in dla silni. Tak więc wejście 10/9daje wyjście (∇2*∇5)/(∇3)^3do reprezentowania (2!*5!)/(3!)^3.

Jest to krótsze, ponieważ pomijamy drugą część funkcji.

+2 bajty: zadanie f=Firstnależy wykonać w odpowiednim miejscu, aby Mathematica nie zdenerwował się.

-8 bajtów: naprawiono błąd dla liczb całkowitych, który faktycznie skrócił kod.

-15 bajtów: FactorIntegerzwraca posortowane dane wyjściowe, z których możemy skorzystać.

-46 bajtów: tak naprawdę nie musimy być sprytni.

Python 2, 220 202 195 183 bajtów

g=lambda a,b:a and g(b%a,a)or b;n,d=input();m=c=()
while n+d>2:
 t=n*d;f=p=2
 while t>p:
	if t%p:p+=1;f*=p
	else:t/=p
 if n%p:c+=p,;n*=f
 else:m+=p,;d*=f
 t=g(n,d);n/=t;d/=t
print m,c

Wypróbuj online! Edycja: Zapisano 18 25 bajtów dzięki @ Mr.Xcoder. Zaoszczędź 12 bajtów dzięki @JonathanFrech.