Zadanie 1

Zapisz w wybranej przez siebie notacji (w postaci pseudokodupseudokodpseudokodu lub w wybranym języku programowania) algorytm, który dla danej liczby x obliczy sumę jej parzystych czynników pierwszych. Maksymalna liczba punktów za rozwiązanie zadania zostanie przyznana, jeśli algorytm wykona $O(\log x)$ operacji arytmetycznych, wymienionych w uwadze.

Specyfikacja problemu:

Dane:

• x – liczba naturalna, której sumę parzystych czynników pierwszych należy obliczyć

Wynik:

• wynik – suma parzystych czynników pierwszych liczby x

Rozwiązanie

Jedynym parzystym czynnikiem pierwszym danej liczby może być 2, ponieważ 2 to jedyna parzysta liczba pierwsza.

Jeżeli liczba x jest nieparzysta, to nie ma żadnych parzystych czynników pierwszych, zwracamy więc 0. Jeżeli liczba x jest parzysta, to dzielimy liczbę przez 2, aż stanie się niepodzielna przez 2. Na koniec zwracamy wynik, czyli liczbę 2 pomnożoną przez liczbę jej wystąpień jako czynnika pierwszego danej liczby.

funkcja sumaPierwszych(x):
	jeżeli x mod 2 = 1:
    	zwróć 0
	suma = 0    
    dopóki x mod 2 = 0:
    	suma ← suma + 2
        x ← x div 2
	zwróć suma

Zauważenie, że jedynym parzystym czynnikiem pierwszym danej liczby może być 2, ułatwia rozwiązanie zadania.

Za przedstawione rozwiązanie dostaniemy maksymalną liczbę punktów, ponieważ jego złożoność wynosi $O(\log x)$.

Słownik