Puzzle programistyczne: problem 3

Te puzzle programistyczne są bardzo wciągające. Rozwiązałem kolejny problem. Kod na repozytorium, a opis poniżej.

Czynniki pierwsze liczby 13195 to 5, 7, 13 i 29.

Znajdź największy czynnik pierwszy liczby 600851475143?

Ja zrobiłem to w taki sposób, że najpierw sprawdzałem czy liczba nie jest pierwsza, jeżeli tak to sama dla siebie jest już czynnikiem pierwszym. Jeżeli nie była pierwsza, to pobierałem kolejną liczbę pierwszą i sprawdzałem czy dzielą się bez reszty. Następnie po znalezieniu podzielnika, wykonuję dzielenie i wynik jest nową liczbą, proces się powtarza.

Na początku chciałem iść na łatwiznę i zadeklarować skończoną tablicę liczb pierwszych, z której bym pobierał kolejno i sprawdzał czy jest podzielnikiem. Szybko się skończyły jednak liczby w tablicy, więc musiałem napisać funkcje: is_prime, next_prime, reset_prime. Ostatnie to tak dla uporządkowania, resetuje “pamięć” next_prime do 2, czyli początku. next_prime sprawdza co było zapisane i generuje następną liczbę pierwszą. is_prime sprawdza czy podana liczba jest pierwsza.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s