Rzecz z Projektem Euler polega na tym, że zazwyczaj istnieje oczywista metoda brutalnej siły, która rozwiązuje problem, co zajmie trochę czasu. Ponieważ pytania stają się coraz trudniejsze, będziesz musiał wdrożyć sprytne rozwiązania.
Jednym ze sposobów rozwiązania tego problemu jest użycie pętli, która zawsze znajduje najmniejszy (dodatnią liczbę całkowitą) współczynnik liczby. Kiedy najmniejszym czynnikiem liczby jest ta liczba, to znalazłeś największy czynnik pierwszy!
Szczegółowy opis algorytmu:
Można to zrobić poprzez utrzymywanie trzy zmienne:
Liczba próbujesz Factor (A) Aktualna sklep dzielnik (B) największy sklep dzielnik (C)
Początkowo niech (A) będzie numerem, który Cię interesuje - w tym przypadku jest to 600851475143. Następnie pozwól (B) być 2. Mieć warunkowe, które sprawdza, czy (A) jest podzielna przez (B) . Jeśli jest podzielna, podziel (A) przez (B), zresetuj (B) na 2 i wróć do sprawdzenia, czy (A) jest podzielna przez (B). Inaczej, jeśli (A) nie jest podzielna przez (B), inkrement (B) o +1, a następnie sprawdź, czy (A) jest podzielna przez (B). Uruchom pętlę do momentu, w którym (A) wynosi 1. Zwrócony (3) będzie największym dzielnikiem głównym o wartości 600851475143.
Istnieje wiele sposobów, które można uczynić bardziej skutecznymi - zamiast zwiększać do następnej liczby całkowitej, można Zwiększenie do następnej koniecznej liczby całkowitej, a zamiast utrzymywania największego sklepu z dzielnikami, możesz po prostu zwrócić bieżący numer, gdy jego jedynym dzielnikiem jest sam. Jednak algorytm, który opisałem powyżej, będzie działał w sekundach niezależnie.
Realizacja w pytona jest następujący: -
def lpf(x):
lpf = 2;
while (x > lpf):
if (x%lpf==0):
x = x/lpf
lpf = 2
else:
lpf+=1;
print("Largest Prime Factor: %d" % (lpf));
def main():
x = long(raw_input("Input long int:"))
lpf(x);
return 0;
if __name__ == '__main__':
main()
przykład: Znajdźmy największą doskonałą czynnik 105 przy użyciu metody opisanej powyżej.
Niech (A) = 105. (B) = 2 (zawsze zaczynamy od 2) i nie mamy jeszcze wartości dla (C).
Czy (A) jest podzielna przez (B)? Nie. Przyrost (B) o +1: (B) = 3. Czy jest (A) podzielna przez (B)? Tak. (105/3 = 35). Największy dzielnik jak dotąd znaleziony to 3. Let (C) = 3. Update (A) = 35. Reset (B) = 2.
Teraz jest (A) podzielny przez (B)? Nie. Przyrost (B) o +1: (B) = 3. Czy (A) jest podzielna przez (B)? Nie. Przyrost (B) o +1: (B) = 4. Czy (A) jest podzielna przez (B)? Nie. Przyrost (B) o +1: (B) = 5. Czy (A) jest podzielny przez (B)? Tak. (35/5 = 7). Największy dzielnik, jaki znaleźliśmy poprzednio, jest przechowywany w (C). (C) jest obecnie 3,5 jest większy niż 3, więc aktualizujemy (C) = 5. Aktualizujemy (A) = 7. Resetujemy (B) = 2.
Następnie powtarzamy proces dla (A), ale będziemy po prostu kontynuować inkrementację (B) aż do (B) = (A), ponieważ 7 jest liczbą pierwszą i nie ma dzielników innych niż ona sama i 1. (Mogliśmy już zatrzymaj się, gdy (B)> ((A)/2), ponieważ nie możesz mieć dzielników całkowitych większych niż połowa liczby - najmniejszy możliwy dzielnik (inny niż 1) dowolnej liczby to 2!)
Tak więc punkt, który zwracamy (A) = 7.
Spróbuj zrobić kilka z nich ręcznie, a dostaniesz powiesić idei
Chciałbym zobaczyć realizację swojej magicznej 'notPrime()' funkcyjnego. :) –
heh, to proste: notPrime (n) = (getLowestDivisiblePrimeNumber (n) == n). –
Szczerze mówiąc, używam tam (prawda), po prostu było to łatwiejsze do wytłumaczenia w ten sposób. Moja metoda getLowestDivisiblePrime odnosi się do klasy podstawowej ArrayList primeList; Jeśli nie istnieje żadna podzielna liczba pierwsza w primeList, znajduje następną liczbę pierwszą do dodania do primeList i kontynuuje to, dopóki nie znajdzie liczby pierwszej, której "liczba" jest dzielona przez (i później odniesie się do większej listy liczb pierwszych) , lub dopóki największa liczba pierwsza w primeList nie jest większa niż sqaureroot "number". Nie ma tam żadnej magii, choć mam nadzieję, że będzie to dość skuteczne. = P –
Jonathan