Myślę, że najłatwiej jest wyjaśnić to wyzwanie w sposób sekwencyjny. Zacznij od liczby N i:
- Znajdź swój najwyższy czynnik główny
- 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 .
- 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)
- 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ększe1i 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
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ć.
2dla N. Następnie otrzymujemy5dla N-1 i61dla N + 1. Następnie dostajemy19za N-2 i67za N + 2. Czy powinniśmy nadal próbować niższych liczb odtąd,19>5czy przestać od tego czasu5<61? Czyli maksima są zachowywane na stronę? (Nie jestem pewien, czy przykład jest matematycznie możliwy).