Najwyższy czynnik pierwszy liczb sąsiednich

13

Myślę, że najłatwiej jest wyjaśnić to wyzwanie w sposób sekwencyjny. Zacznij od liczby N i:

  1. Znajdź swój najwyższy czynnik główny
  2. Sprawdzić numery powyżej i poniżej N i sprawdzić, czy najwyższy współczynnik prime jest wyższa (czyli najwyższy prime czynnikiem N-1 i / lub N + 1 jest wyższy niż współczynnik N .
  3. Kontynuuj sprawdzanie wyższych i / lub niższych liczb sąsiadujących z N w kierunkach, w których rosną najwyższe czynniki ( (N-2, N-3 ...) i / lub (N + 2, N + 3 ...) i tak dalej na)
  4. Gdy nie będzie już żadnych czynników pierwszych w żadnym kierunku, które byłyby wyższe niż te, które już odkryliśmy, zatrzymujemy się i wysyłamy najwyższy czynnik główny, jaki napotkaliśmy.

Spójrzmy na przykład:

245ma czynniki pierwsze 5, 7, 7. Sąsiedzi to:

244 -> 2,  2,  61
245 -> 5,  7,  7
246 -> 2,  3,  41

Najwyższy czynnik pierwszy rośnie w obu kierunkach, więc musimy spojrzeć na następnego sąsiada:

243 -> 3,   3,  3,  3,  3
244 -> 2,   2,  2,  61
245 -> 5,   7,  7
246 -> 2,   3,  41
247 -> 13,  19

Najwyższe czynniki pierwsze maleją teraz w obu kierunkach, więc najwyższy czynnik pierwszy, jaki napotkaliśmy, jest 61i dlatego powinien zostać zwrócony.

Inny przykład:

Spójrzmy na 1024. Jego główne czynniki to 2, 2, 2, 2, 2, 2, 2, 2, 2, 2. Głównymi czynnikami jego najbliższych sąsiadów są:

1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41

Najwyższy współczynnik pierwszy rośnie w obu kierunkach, od 2do 31lub 41. Spójrzmy na sąsiadów:

1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

Najwyższy czynnik pierwszy dla 1022to 73, a najwyższy czynnik pierwszy dla 1026to 19. Ponieważ 19jest niższy niż 41nie jesteśmy nim zainteresowani. Wciąż rośnie dla liczb mniejszych niż N, więc sprawdzimy następny w tym kierunku :

1021 -> 1021
1022 -> 2, 7,  73
1023 -> 3, 11, 31
1024 -> 2,  2,  2,  2,  2,  2,  2,  2,  2,  2
1025 -> 5,  5, 41
1026 -> 2,  3,  3, 19

1021 jest liczbą pierwszą i najwyższą liczbą, jaką napotkaliśmy, więc należy ją zwrócić.

Zasady:

  • Otrzymasz tylko dodatnie wartości Nwiększe 1i mniejsze niż 2^31-2.
  • Formaty wejściowe i wyjściowe są opcjonalne, ale liczby muszą być w bazie 10.
  • Powinieneś kontynuować wyszukiwanie wyższych liczb pierwszych, dopóki najwyższa wartość rośnie w tym kierunku. Kierunki są od siebie niezależne.

Przypadki testowe:

Format: N, highest_factor

2, 3
3, 3
6, 7
8, 11
24, 23 
1000, 997
736709, 5417 
8469038, 9431
Stewie Griffin
źródło
Powiedzmy, że otrzymujemy najwyższy współczynnik pierwszy 2dla N. Następnie otrzymujemy 5dla N-1 i 61dla N + 1. Następnie dostajemy 19za N-2 i 67za N + 2. Czy powinniśmy nadal próbować niższych liczb odtąd, 19>5czy przestać od tego czasu 5<61? Czyli maksima są zachowywane na stronę? (Nie jestem pewien, czy przykład jest matematycznie możliwy).
PurkkaKoodari
@ Pietu1998, czy pytanie jest teraz bardziej jasne?
Stewie Griffin,
N=2wydaje się, że jest to przypadek skrajny, ponieważ 1nie ma czynników pierwotnych, więc nie ma maksymalnego czynnika pierwotnego, z którym moglibyśmy porównać, aby zdecydować, czy powinniśmy kontynuować.
Jonathan Allan

Odpowiedzi:

4

Mathematica, 82 74 bajty

Dzięki Martin Ender za oszczędność 8 bajtów!

Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&

Nienazwana funkcja pobierająca liczbę całkowitą i zwracająca liczbę całkowitą.

±n_:=#//.x_/;l[t=x+n]>l@x:>tdefiniuje funkcję jednoargumentową, ±która zwiększa wejściową liczbę całkowitą funkcji globalnej ntak długo, jak długo rośnie największy czynnik pierwszy. (Funkcja największego czynnika pierwszego jest zdefiniowana za pomocą l=FactorInteger[#][[-1,1]]&.) {±-1,±1}Dlatego stosuje tę funkcję dwukrotnie do wejściowej liczby całkowitej, z przyrostem -1i ponownie z przyrostem 1. Następnie Max@@(...l...)/@...bierze większy z dwóch znalezionych w ten sposób największych czynników pierwszych.

Poprzednie zgłoszenie:

Max@@(l=FactorInteger[#][[-1,1]]&)/@(#//.x_/;l[t=x+#2]>l[x]:>t&@@@{{#,-1},{#,1}})&
Greg Martin
źródło
Zaoszczędziłem kilka bajtów, unikając @@@(i można l@xtam użyć ):Max@@(±n_:=#//.x_/;l[t=x+n]>l@x:>t;l=FactorInteger[#][[-1,1]]&)/@{±-1,±1}&
Martin Ender
1

Perl, 137 bajtów

122 bajty kodu + 15 bajtów dla -pi -Mntheory=:all.

sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_

Aby uruchomić:

perl -pMntheory=:all -e 'sub f{$t=(factor$_+pop)[-1]}$i=$j=1;while($i|$j){f++$c;($i&=$t>$h)&&($h=$t);f-$c;($j&=$t>$l)&&($l=$t)}$_=$h>$l?$h:$l?$l:$_' <<< 736709

Jeśli nie masz ntheoryzainstalowanego, możesz go zainstalować, wpisując (echo y;echo) | perl -MCPAN -e 'install ntheory'terminal.

Dada
źródło
0

Ruby, 99 bajtów

->n{f=->n{i=2;n%i<1?n/=i:i+=1while i<n;n};g=->s,z{s+=z while f[s+z]>b=f[s];b};[g[n,1],g[n,-1]].max}

Wyjaśnienie:

  • f () jest najwyższym czynnikiem podstawowym
  • g () to funkcja szukająca sąsiadów w jednym kierunku
  • zastosuj g do (n, -1) i (n, + 1), aby wyszukać w obu kierunkach
GB
źródło