Regex (ECMAScript), 276 205 201 193 189 bajtów
Porównywanie wielokrotności (wykładników) różnych czynników pierwszych jest interesującym problemem do rozwiązania za pomocą wyrażenia regularnego ECMAScript - brak odniesień wstecznych, które utrzymują się przez iteracje pętli, sprawia, że liczenie wszystkiego jest trudne. Nawet jeśli policzenie omawianej cechy numerycznej jest możliwe, często bardziej pośrednie podejście zapewnia lepsze golfa.
Podobnie jak w przypadku moich innych wpisów regularnych ECMA, dam ostrzeżenie spoilerowe: Gorąco zalecam nauczenie się rozwiązywania pojedynczych problemów matematycznych w wyrażeniu regularnym ECMAScript. To była dla mnie fascynująca podróż i nie chcę zepsuć jej nikomu, kto mógłby potencjalnie chcieć spróbować samemu, szczególnie tym, którzy interesują się teorią liczb. W tym wcześniejszym poście znajduje się lista zalecanych problemów oznaczonych spoilerem do rozwiązania jeden po drugim.
Więc nie czytaj dalej, jeśli nie chcesz, aby zepsuła Ci się jakaś zaawansowana magia wyrażeń regularnych . Jeśli chcesz spróbować samodzielnie odkryć tę magię, zdecydowanie polecam zacząć od rozwiązania niektórych problemów z wyrażeniem regularnym ECMAScript, jak opisano w linku powyżej.
Główny ładunek z regexu, który wcześniej opracowałem, okazał się bardzo odpowiedni do tego wyzwania. To jest wyrażenie regularne, które znajduje liczbę pierwszą o największej krotności . Moje pierwsze rozwiązanie tego problemu było bardzo długie, a później grałem w golfa etapami, najpierw przepisując go, aby użyć molekularnego spojrzenia , a następnie przenosząc go z powrotem do zwykłego ECMAScript za pomocą zaawansowanej techniki, aby obejść brak molekularnej perspektywy , a następnie gra w golfa jest znacznie mniejsza niż oryginalne proste rozwiązanie ECMAScript.
Część tego wyrażenia regularnego, która dotyczy tego problemu, jest pierwszym krokiem, w którym znajduje się Q, najmniejszy czynnik N, który dzieli wszystkie swoje czynniki pierwsze. Gdy już otrzymamy tę liczbę, wszystko, co musimy zrobić, aby pokazać, że N jest „liczbą o stałym wykładniku”, dzieli N przez Q, dopóki nie możemy dłużej; jeśli wynik wynosi 1, wszystkie liczby pierwsze są równe wielokrotności.
Po przesłaniu odpowiedzi przy użyciu mojego wcześniej opracowanego algorytmu znajdowania Q, zdałem sobie sprawę, że można go obliczyć w zupełnie inny sposób: Znajdź największy współczynnik kwadratowy N (używając tego samego algorytmu jak mój regex liczby Carmichaela ). Jak się okazuje, nie stanowi to żadnego problemu * pod względem obejścia braku molekularnego spojrzenia przed siebie i spojrzenia o zmiennej długości (nie trzeba wciągać wcześniej stosowanej techniki zaawansowanej) i jest o 64 bajty krótszy! Dodatkowo eliminuje to złożoność traktowania bezkwadratowego N i pierwszej N jako różnych specjalnych przypadków, usuwając kolejne 7 bajtów z tego rozwiązania.
(Nadal istnieją inne problemy, które wymagają zaawansowanej techniki używanej wcześniej do obliczania Q, ale obecnie żaden z nich nie jest reprezentowany przez moje posty PPCG).
Test wielokrotności stawiam przed testem kolejnych liczb pierwszych, ponieważ ten drugi jest znacznie wolniejszy; umieszczenie testów, które mogą szybciej zakończyć się niepowodzeniem, sprawia, że wyrażenie regularne jest szybsze dla równomiernie rozłożonego wejścia. Lepiej jest też postawić golfa na pierwszym miejscu, ponieważ wykorzystuje on więcej odwołań wstecznych (co kosztowałoby więcej, gdyby były dwucyfrowe).
Byłem w stanie usunąć 4 bajty z tego wyrażenia regularnego (193 → 189), używając sztuczki znalezionej przez Grimy'ego, która może dalej skracać podział w przypadku, gdy iloraz gwarantowany jest większy lub równy dzielnikowi.
^(?=(|(x+)\2*(?=\2$))((?=(xx+?)\4*$)(?=(x+)(\5+$))\6(?!\4*$))*x$)(?=.*$\2|((?=((x*)(?=\2\9+$)x)(\8*$))\10)*x$)(?!(((x+)(?=\13+$)(x+))(?!\12+$)(x+))\11*(?=\11$)(?!(\15\14?)?((xx+)\18+|x?)$))
Wypróbuj online!
# For the purposes of these comments, the input number = N.
^
# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \2.
# If N is square-free, \2 will be unset.
(?=
# Search through all factors of N, from largest to smallest, searching for one that
# satisfies the desired property. The first factor tried will be N itself, for which
# \2 will be unset.
(|(x+)\2*(?=\2$)) # for factors < N: \2 = factor of N; tail = \2
# Assert that tail is square-free (its prime factors all have single multiplicity)
(
(?=(xx+?)\4*$) # \4 = smallest prime factor of tail
(?=(x+)(\5+$)) # \5 = tail / \4 (implicitly); \6 = tool to make tail = \5
\6 # tail = \5
(?!\4*$) # Assert that tail is no longer divisible by \4, i.e. that that
# prime factor was of exactly single multiplicity.
)*x$
)
# Step 2: Require that either \2 is unset, or that the result of repeatedly
# dividing tail by \2 is 1.
(?=
.*$\2
|
(
# In the following division calculation, we can skip the test for divisibility
# by \2-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
# capture \2-1 above, and can use a better-golfed form of the division.
(?=
( # \8 = tail / \2
(x*) # \9 = \8-1
(?=\2\9+$)
x
)
(\8*$) # \10 = tool to make tail = \8
)
\10 # tail = \8
)*
x$ # Require that the end result is 1
)
# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
(?!
( # \11 = a factor of N
( # \12 = a non-factor of N between \11 and \13
(x+)(?=\13+$) # \13 = a factor of N smaller than \11
(x+) # \14 = tool (with \15) to make tail = \13
)
(?!\12+$)
(x+) # \15 = tool to make tail = \12
)
\11*(?=\11$) # tail = \11
# Assert that \11, \12, and \13 are all prime
(?!
(\15\14?)? # tail = either \11, \12, or \13
((xx+)\18+|x?)$
)
)
* Jest jeszcze czystszy z molekularnym spojrzeniem w przód, bez specjalnego przypadku, w którym N nie ma kwadratu. To zrzuca 6 bajtów, co daje 195 187 183 bajtów :
^(?=(?*(x+))\1*(?=\1$)((?=(xx+?)\3*$)(?=(x+)(\4+$))\5(?!\3*$))*x$)(?=((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$)(?!(((x+)(?=\12+$)(x+))(?!\11+$)(x+))\10*(?=\10$)(?!(\14\13?)?((xx+)\17+|x?)$))
# For the purposes of these comments, the input number = N.
^
# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \1.
(?=
(?*(x+)) # \1 = proposed factor of N
\1*(?=\1$) # Assert that \1 is a factor of N; tail = \1
# Assert that tail is square-free (its prime factors all have single multiplicity)
(
(?=(xx+?)\3*$) # \3 = smallest prime factor of tail
(?=(x+)(\4+$)) # \4 = tail / \3 (implicitly); \5 = tool to make tail = \4
\5 # tail = \4
(?!\3*$) # Assert that tail is no longer divisible by \3, i.e. that that
# prime factor was of exactly single multiplicity.
)*x$
)
# Step 2: Require that the result of repeatedly dividing tail by \1 is 1.
(?=
(
# In the following division calculation, we can skip the test for divisibility
# by \1-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
# capture \1-1 above, and can use a better-golfed form of the division.
(?=
( # \7 = tail / \1
(x*) # \8 = \7-1
(?=\1\8+$)
x
)
(\7*$) # \9 = tool to make tail = \7
)
\9 # tail = \7
)*
x$ # Require that the end result is 1
)
# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
(?!
( # \10 = a factor of N
( # \11 = a non-factor of N between \10 and \12
(x+)(?=\12+$) # \12 = a factor of N smaller than \10
(x+) # \13 = tool (with \14) to make tail = \12
)
(?!\11+$)
(x+) # \14 = tool to make tail = \11
)
\10*(?=\10$) # tail = \10
# Assert that \10, \11, and \12 are all prime
(?!
(\14\13?)? # tail = either \10, \11, or \12
((xx+)\17+|x?)$
)
)
Tutaj jest przeniesiony do look-look za zmienną długością:
Regex (ECMAScript 2018), 198 195 194 186 182 bajtów
^(?=(x+)(?=\1*$)(?<=^x((?<!^\5*)\3(?<=(^\4+)(x+))(?<=^\5*(x+?x)))*))((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$(?<!(?!(\14\16?)?((xx+)\12+|x?)$)(?<=^\13+)((x+)(?<!^\15+)((x+)(?<=^\17+)(x+))))
Wypróbuj online!
# For the purposes of these comments, the input number = N.
^
# Assert that all of N's prime factors are of equal multiplicity
# Step 1: Find Q, the largest square-free factor of N (which will also be the smallest
# factor of N that has all the same prime factors as N) and put it in \1.
(?=
(x+)(?=\1*$) # \1 = factor of N; head = \1
(?<= # This is evaluated right-to-left, so please read bottom to top.
^x
(
(?<!^\5*) # Assert that head is no longer divisible by \6, i.e. that
# that prime factor was of exactly single multiplicity.
\3 # head = \4
(?<=(^\4+)(x+)) # \4 = head / \5 (implicitly); \3 = tool to make head = \4
(?<=^\5*(x+?x)) # \5 = smallest prime factor of head
)*
)
)
# Step 2: Require that the result of repeatedly dividing tail by \1 is 1.
(
# In the following division calculation, we can skip the test for divisibility
# by \1-1 because it's guaranteed that \2 <= \8. As a result, we did not need to
# capture \1-1 above, and can use a better-golfed form of the division.
(?=
( # \7 = tail / \1
(x*) # \8 = \7-1
(?=\1\8+$)
x
)
(\7*$) # \9 = tool to make tail = \7
)
\9 # tail = \7
)*
x$ # Require that the end result is 1
# Assert that there exists no trio of prime numbers such that N is divisible by the
# smallest and largest prime but not the middle prime.
# This is evaluated right-to-left, so please read bottom to top, but switch back to
# reading top to bottom at the negative lookahead.
(?<!
# Assert that \13, \15, and \17 are all prime.
(?!
(\14\16?)? # tail = either \13, \15, or \17
((xx+)\12+|x?)$
)
(?<=^\13+)
( # tail = \13
(x+) # \14 = tool to make tail = \15
(?<!^\15+)
(
(x+) # \16 = tool (with \14) to make tail = \17
(?<=^\17+)(x+) # \17 = a factor of N smaller than \13
) # \15 = a non-factor of N between \13 and \17
) # \13 = a factor of N
)