Zadanie 1. Sumy czynników pierwszych

Marcin od dziecka interesował się liczbami. Gdy w liceum zaczął uczyć się informatyki na poziomie rozszerzonym, chętnie eksplorował różne właściwości liczb. Postanowił wygenerować losowo 200 liczb naturalnych.

W pliku liczby.txt znajduje się 200 różnych liczb naturalnych o długości od 1 do 6 cyfr, każda w osobnej linii. Liczby należą do przedziału $<8, 999951>$.

Marcin chce się dowiedzieć, ile wynosi suma czynników pierwszych każdej z wygenerowanych przez niego liczb.

Dla każdej liczby z pliku liczby.txt podaj sumę jej czynników pierwszych. Wynik zapisz w pliku wynik.txt, każdą sumę w osobnym wierszu, zachowaj kolejność z pliku liczby.txt.

420
69
88

19
26
17

Do oceny oddajesz:

• plik wynik.txt zawierający odpowiedź do zadania (sumy czynników pierwszych liczb z pliku liczby.txt, każda w osobnej linii, w kolejności zgodnej z plikiem liczby.txt);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie:

W rozwiązaniu użyjemy algorytmu rozkładu liczby na czynniki pierwsze. Zapiszemy go w funkcji pomocniczej, która będzie zwracała sumę wszystkich znalezionych czynników pierwszych.

Przykładowa funkcja może wyglądać następująco:

funkcja suma_czynników_pierwszych(x):
	jeżeli x < 2:
    	zwróć 0

	suma ← 0
    
    dopóki x mod 2 = 0:
    	suma ← suma + 2
        x ← x div 2
        
    dla i = 3, 5, ..., całk(pierwiastek(x) + 1):
    	dopóki x mod i = 0:
        	suma ← suma + i
            x ← x div i
            
    jeżeli x > 2:
    	suma ← suma + x
        
    zwróć suma

• Funkcja przyjmuje jako argument x [linia kodu 1], oznaczający liczbę do sprawdzenia. Za każdym razem, gdy znajdziemy czynnik pierwszy, będziemy go dodawali do zmiennej suma, a samą liczbę dzielili przez niego.

• Sprawdzamy, czy liczba jest mniejsza od 2, czyli czy ma wartość 0 albo 1 [linia kodu 2]. Jeśli tak, zwracamy 0, ponieważ liczby te nie mają żadnych czynników pierwszych w swoim rozkładzie [linia kodu 3]. W przypadku naszego pliku najmniejsza liczba to 8, ale twój program powinien działać dla dowolnego zestawu danych.

• Inicjujemy zmienną suma i przypisujemy jej wartość 0 [linia kodu 5].

• Tworzymy pętlę dopóki, która będzie się wykonywać tak długo, dopóki wynik dzielenia x przez 2 będzie liczbą parzystą [linia kodu 7]. Gdy wynik dzielenia jest liczbą parzystą, do zmiennej suma dodajemy 2 [linia kodu 8]. Następnie zmiennej x przypisujemy wynik dzielenia całkowitego x przez 2 [linia kodu 9].

• Następnie szukamy nieparzystych czynników pierwszych. Tworzymy zatem pętlę dla [linia kodu 11]. Zaczynamy od liczby 3 i sprawdzamy, czy x jest przez nią podzielne. Jeśli tak, do zmiennej suma dodajemy wartość zmiennej i [linia kodu 13]. Następnie zmiennej x przypisujemy wynik dzielenia całkowitego x przez i. Kontynuujemy działanie pętli dopóki x jest podzielne przez analizowany potencjalny czynnik pierwszy. Następnie zwiększamy sprawdzaną liczbę o 2, ponieważ we wcześniejszej pętli wyeliminowaliśmy wszelkie parzyste czynniki. Powtarzamy procedurę, aż dojdziemy do pierwiastka liczby x.

• Jeżeli po zakończeniu poprzedniej pętli liczba jest wciąż większa od 2 [linia kodu 16], oznacza to, że sprawdzana liczba od samego początku była pierwszaliczba pierwszapierwsza. Dodajemy ją więc do zmiennej suma [linia kodu 17].

• Na samym końcu zwracamy zmienną suma [linia kodu 19].

liczby[0..199] ← wczytaj dane z pliku "liczby.txt"
 
dla i = 0, 1, ..., 199 wykonuj:
	suma ← suma_czynników_pierwszych(liczby[i])
	dopisz suma do pliku “wynik.txt"
    
zamknij plik "wynik.txt"
zamknij plik "liczby.txt"

Wczytujemy liczby z pliku do tablicy [linia kodu 1]. Następnie dla każdej liczby [linia kodu 3] wywołujemy funkcję suma_czynników_pierwszych oraz wypisujemy wartość zmiennej suma do pliku wynikowego [linia kodu 5].

Na końcu zamykamy pliki [linie kodu 7 i 8].

Odpowiedź

Dla danych z pliku liczby.txt poprawny plik wynik.txt wygląda następująco:

Słownik