Rok 2013 ma zasadnicze znaczenie 3*11*61
. 2014 ma pierwszoplanową faktoryzację 2*19*53
. Interesująca nieruchomość dotyczące tych factorizations jest to, że istnieją różne liczby pierwsze w factorizations 2013 i 2014, że suma na ten sam numer: 11+61=19+53=72
.
Napisz program lub funkcję, która przyjmuje na wejściu dwie dodatnie liczby całkowite większe od 1 i zwraca prawdziwą wartość, jeśli istnieje suma wybranych czynników pierwszych jednej liczby, która jest równa sumie wybranych czynników pierwszych w drugiej liczbie, oraz w przeciwnym razie wartość falsey.
Wyjaśnienia
- Można użyć więcej niż dwóch głównych czynników. Nie wszystkie czynniki pierwsze liczby muszą być użyte w sumie. Nie jest konieczne, aby liczba liczb pierwszych używanych z dwóch liczb była równa.
- Nawet jeśli liczba pierwsza zostanie podniesiona do pewnej potęgi większej niż 1 w rozkładzie liczb na liczbę, można jej użyć tylko raz w sumie liczb pierwszych dla liczby.
- 1 nie jest liczbą pierwszą.
- Obie liczby wejściowe będą mniejsze niż
2^32-1
.
Przypadki testowe
5,6
5=5
6=2*3
5=2+3
==>True
2013,2014
2013=3*11*61
2014=2*19*53
11+61=19+53
==>True
8,15
8=2^3
15=3*5
No possible sum
==>False
21,25
21=3*7
25=5^2
No possible sum (can't do 3+7=5+5 because of exponent)
==>False
To jest kod golfowy. Obowiązują standardowe zasady. Najkrótszy kod w bajtach wygrywa.
true
ponieważ dzielą ten czynnik7
?Odpowiedzi:
Julia,
9593 bajtówPodstawową funkcją jest
f
i wywołuje funkcję pomocnikag
.Nie golfowany:
Zaoszczędzono 2 bajty dzięki Darth Alephalpha
źródło
map(p->map
jest krótszy niż(m=map)(p->m
.Pyth, 11 bajtów
Wprowadź w formularzu
30,7
.źródło
Pyth -
171211 bajtówDzięki @FryAmTheEggman za ustalenie mojej odpowiedzi i zapisanie bajtu.
Pakiet testowy .
źródło
ty
działa i oszczędza do widzenia?Haskell,
115106 bajtówPrzykład użycia:
2013 # 2014
->True
.p
tworzy listę wszystkich głównych czynników argumentu, usuwa duplikaty, tworzy listę wszystkich podsekwencji, upuszcza pierwszą (która zawsze jest pustą listą) i na koniec sumuje podsekwencje.#
sprawdza, czyp a
nie jest równa różnicyp a \\ p b
. Jeśli nie są równe, mają co najmniej jeden wspólny element.źródło
Japt, 25 bajtów
Wyjścia
true
lubfalse
. Wypróbuj online!Bez golfa i wyjaśnienia
Aby uzyskać dodatkowy bajt, możesz podzielić kod faktoryzujący-unikalny-połączyć-sumę między oba dane wejściowe, z dodatkową zaletą posiadania złożoności czasowej
O(O(25-byte version)^2)
:źródło
CJam, 23 bajty
Sprawdź to tutaj.
Prawda będzie sumą wszystkich wspólnych sum, wartość fałsz jest pustym ciągiem.
Wyjaśnienie
źródło
Brachylog ,
109 bajtówWypróbuj online!
Predykat pomyślnie zwróci,
[the sum, the sum]
jeśli istnieje, i nie powiedzie się, jeśli suma nie istnieje.-1 bajt dzięki Fatalize (twórcy Brachylog) przypominając mi, że istnieje meta-predykat weryfikacji .
źródło
ᵛ - verify
zamiastˢ=
zapisać jeden bajt.MATL , 23 bajty
Wykorzystuje bieżącą wersję 2.0.2 , która jest wcześniejsza niż to wyzwanie.
Liczby podano jako dwa osobne dane wejściowe. Dane wyjściowe to
0
lub1
.Przykład
Wyjaśnienie
źródło
Mathematica, 58 bajtów
Wyjaśnienie:
To anonimowa funkcja.
Najpierw
IntersectingQ
sprawdza, czy przecinają się dwie listy. Ale dane wejściowe są liczbami zamiast listami, więc pozostają bezcenne. Na przykład, jeśli dane wejściowe są2013
i2014
, a następnieIntersectingQ@##&
wracaIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
to kolejna anonimowa funkcja, która pobiera liczbę całkowitą, pobiera listę czynników pierwszych bez powtórzeń, pobiera zestaw mocy, usuwa pusty zbiór, a następnie pobiera sumę każdego zestawu. WięcTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
wraca{3, 11, 61, 14, 64, 72, 75}
.Następnie odwzoruj
Tr/@Rest@Subsets[#&@@@FactorInteger@#]&
wyrażenieIntersectingQ[2013, 2014]
.Tr/@Rest@Subsets[#&@@@FactorInteger@#]&[2013]
iTr/@Rest@Subsets[#&@@@FactorInteger@#]&[2014]]
są listami, więc tym razem możemy uzyskać wynik zbierania.źródło
IntersectingQ
pierwszy jest niesamowity! :)PARI / GP , 98 bajtów
Współczynnik, grab primes (
[,1]
), zapętlaj niepuste podzbiory, suma i uniq, a następnie przecinaj wynik tego dla dwóch liczb. Zwrócona wartość to liczba skrzyżowań, co jest prawdą, chyba że są równe 0.źródło
APL (Dyalog Extended) ,
2317 bajtów SBCS-5 dzięki ngn
Anonimowa funkcja ukrytej poprawki.
Wypróbuj online!
⍥{
…}
Zastosuj następującą anonimową funkcję do obu argumentów:⍭
czynniki pierwsze⍤
następnie∪
jedyne w swoim rodzaju0+⍀.,
redukcja tabeli dodawania o zero połączona z każdym czynnikiem∊
ε nlist (spłaszczyć)∩
skrzyżowanie⍤
następnie≢
suma tych1<
czy jest więcej niż jeden? (jeden, ponieważ sumy żadnych czynników)źródło
p+.×⊤1↓⍳2*≢p←
->1↓∊(⊢,+)/0,⍨
1↓∊∘.+/0,¨
1↓∊0∘.+.,
produktem inouter - jak często to widzisz :)⍥
dobrze rozumiem , to też powinno działać:1<∘≢∩⍥{∊0∘.+.,∪⍭⍵}
05AB1E ,
108 bajtów-2 bajty dzięki @Emigna .
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło
f€æO`å¦à
powinien działać dla 8.Japt, 12 bajtów
Uruchom to online
źródło
Python 3 , 206 bajtów
Jest to funkcja lambda (m), która przyjmuje 2 liczby i zwraca zestaw zawierający dowolne sumy czynników pierwszych, które mają ze sobą wspólnego. W Pythonie jest to prawdziwa wartość, gdy nie jest pusta, i wartość falsey, gdy jest pusta.
Edycja: Okazało się, że moja pierwotna odpowiedź nie działała dla głównych danych wejściowych, jak wskazał @JoKing. Zostało to naprawione (wraz z kilkoma innymi błędami) przy tragicznym koszcie 40 bajtów.
Szybkie wyjaśnienie za pomocą komentarzy:
Wypróbuj online!
źródło
5,6
, ponieważ nie obsługuje głównych danych wejściowychAPL (NARS), 50 znaków, 100 bajtów
tutaj π znalazłby szereg czynników w swoim argumencie;
byłaby funkcja znajdująca wszystkie podzbiory ... muszę powiedzieć, że wydaje się, że {⍵operator itsArguments} ¨ (dla każdego lewego) i ¨ (dla każdego prawego) może imitować pętlę o ustalonej liczbie cykli i ¨¨ jest w porządku aby zobaczyć podzbiory jednego zestawu ... ten sposób widzenia wydaje się redukować symbole w opisie pętli ...; test
Jedna mała analiza:
źródło
Japt
-¡
, 14 bajtówZaoszczędź 3 bajty dzięki @Shaggy
Spróbuj
źródło
ÎfUÌ l
albo krótszy wciążrf l
.rø
byłby to najkrótszy sposób, ale Oliver cię do tego pobił.Galaretka ,
189 bajtówWypróbuj online!
Dzięki @Jonathan Allan za -9 i niesamowitą pomoc :).
Pobiera dane wejściowe jako tablicę dwóch elementów. Objaśnienie kodu:
¹
źródło
,
.ẒƇ
Jest zbędny, nie ma non-prime prime-czynników. ToÆFḢ€
jest po prostuÆf
, z tym wyjątkiem, że to drugie daje nam powtórzenia, których moglibyśmy potrzebować, na przykład26=2*13
i na125=5*5*5
chwilę2+13=5+5+5
. Mimo to jednakẆ
nie jest wystarczająco dobry, na przykład zamiast26
użycia,182=2*7*13
który również powinien to znaleźć,2+13=5+5+5
ale nie - zamiast tego chcemy power-set (ŒP
) bez wiodącego, pustego elementu (możemy użyćḊ
).S€
tutaj można zastąpić§
. - Prawdopodobnie możesz zapisać bajty za pomocą$
iƊ
-.)
a wraz z moimi poprawkami, aby działał poprawnie (plus zastąpienieœ&
gof
), kod ma 9 bajtów:ÆfŒPḊ§)f/
spróbujGaia ,
1611 bajtówWypróbuj online!
Górna funkcja (pierwsza linia) oblicza sumy zestawu mocy czynników pierwszych, a druga funkcja sprawdza, czy którykolwiek z elementów przecięcia jest niezerowy.
źródło