Regex (ECMAScript), 131 bajtów
Co najmniej -12 bajtów dzięki Deadcode (na czacie)
(?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x
Wypróbuj online!
Dane wyjściowe to długość dopasowania.
Wyrażenia regularne ECMAScript sprawiają, że niezwykle trudno jest policzyć cokolwiek. Wszelkie odnośniki zdefiniowane poza pętlą będą stałe podczas pętli, wszelkie odnośniki zdefiniowane w pętli zostaną zresetowane podczas zapętlania. Zatem jedynym sposobem przenoszenia stanu przez iteracje pętli jest użycie bieżącej pozycji dopasowania. To jedna liczba całkowita i może się tylko zmniejszać (no cóż, pozycja rośnie, ale długość ogona maleje i do tego możemy matematyki).
Biorąc pod uwagę te ograniczenia, zwykłe liczenie numerów coprime wydaje się niemożliwe. Zamiast tego używamy formuły Eulera do obliczania sumy.
Oto jak to wygląda w pseudokodzie:
N = input
Z = largest prime factor of N
P = 0
do:
P = smallest number > P that’s a prime factor of N
N = N - (N / P)
while P != Z
return N
Są w tym dwie wątpliwe rzeczy.
Po pierwsze, nie zapisujemy danych wejściowych, tylko bieżący produkt, więc w jaki sposób możemy dostać się do głównych czynników wejściowych? Sztuka polega na tym, że (N - (N / P)) ma takie same czynniki pierwsze> P jak N. Może zyskać nowe czynniki pierwsze <P, ale i tak je ignorujemy. Zauważ, że działa to tylko dlatego, że iterujemy czynniki pierwsze od najmniejszej do największej.
Po drugie, musimy pamiętać o dwóch liczbach w iteracjach pętli (P i N, Z nie liczy się, ponieważ jest stała), a ja właśnie powiedziałem, że to niemożliwe! Na szczęście możemy zamienić te dwie liczby w jednym. Zauważ, że na początku pętli N będzie zawsze wielokrotnością Z, podczas gdy P będzie zawsze mniejsze niż Z. Zatem możemy po prostu zapamiętać N + P i wyodrębnić P za pomocą modulo.
Oto nieco bardziej szczegółowy pseudo-kod:
N = input
Z = largest prime factor of N
do:
P = N % Z
N = N - P
P = smallest number > P that’s a prime factor of N
N = N - (N / P) + P
while P != Z
return N - Z
A oto skomentowany regex:
# \1 = largest prime factor of N
# Computed by repeatedly dividing N by its smallest factor
(?= ( (xx+) (?=\2+$) | x+ )+ )
(?=
# Main loop!
(
# \4 = N % \1, N -= \4
(x*?) (?=\1*$)
# \5 = next prime factor of N
(?= (\4xx+?) (\5* (?!(xx+)\7+$) \5)? $ )
# \8 = N / \5, \9 = \8 - 1, \10 = N - \8
(?= ((x*) (?=\5\9*$) x) (\8*) $ )
x*
(?=
# if \5 = \1, break.
(?=\5$) \1
|
# else, N = (\5 - 1) + (N - B)
\5\10
)
x
)+
) \10
A jako bonus…
Regex (ECMAScript 2018, liczba dopasowań), 23 bajty
x(?<!^\1*(?=\1*$)(x+x))
Wypróbuj online!
Dane wyjściowe to liczba dopasowań. ECMAScript 2018 wprowadza zmienne spojrzenie wstecz (oceniane od prawej do lewej), co pozwala po prostu policzyć wszystkie liczby coprime z danymi wejściowymi.
Okazuje się, że jest to niezależnie ta sama metoda stosowana w rozwiązaniu Retina Leaky Nun , a regex jest nawet tej samej długości ( i zamiennie ). Zostawiam go tutaj, ponieważ może być interesujące, że ta metoda działa w ECMAScript 2018 (a nie tylko .NET).
# Implicitly iterate from the input to 0
x # Don’t match 0
(?<! ) # Match iff there is no...
(x+x) # integer >= 2...
(?=\1*$) # that divides the current number...
^\1* # and also divides the input
