laboratorium: zadanie 2 termin: 21 paz
dziernika 2009 r.
kurs programowania w Javie
rozkład liczb całkowitych na czynniki pierwsze
Instytut Informatyki Uniwersytetu Wrocławskiego Paweł Rzechonek
Zadanie.
Napisz program, który wypisze na standardowym wyjściuSystem.outrozkład zadanych (poprzez argu-
menty wywołania) liczb całkowitych na czynniki pierwsze. Rozkład każdej z nich ma być wypisany w osobnym
wierszu: najpierw liczba, potem znak=i dalej czynniki pierwsze poodzielane znakiem*.
Parametry wywołania programu powinny być liczbami całkowitymi. Odstępstwo od tego wymogu ma
skutkować wypisaniem stosownego komunikatu o błędzie do standardowego strumienia dla błędówSystem.err.
Jeśli program wywołano bez żadnego parametru, to należy wypisać na standardowym strumieniu dla błędów
instrukcję obsługi programu.
Programując to zadanie zdefiniuj w pakiecienarzedziaklasę usługowąLiczbyPierwsze. Klasa ta powinna
posiadać tylko dwie metody statyczne:czyPierwsza()testująca pierwszość liczby inaCzynnikiPierwsze()
tworząca rozkład liczby na czynniki pierwsze. Wykorzystaj do tego celu sito Eratostenesa, modyfikując je
w ten sposób, że dla każdej liczby pamiętaj jej najmniejszy podzielnik pierwszy (będzie to trik pomocny
przy wyliczaniu rozkładu liczby na czynniki pierwsze). Wymienione funkcje powinny udzielać poprawnych
odpowiedzi dla wszystkich liczb typulong(wez
pod uwagę, że nie możesz utworzyć tak dużego sita, więc
zastanów się jak ten problem obejść algorytmicznie). KasaLiczbyPierwszepowinna być tak zdefiniowana,
aby nie można było stworzyć jej instancji.
public class LiczbyPierwsze
{
protected final ststic int POTEGA2 = 21 ;
protected final static long[] SITO = new long[1<// ... potrzebny jest blok inicjalizacyjny dla sita ...
public static boolean czyPierwsza (long x)
{ /* ... */ }
public static long[] naCzynnikiPierwsze (long x)
{ /* ... */ }
}
Uwaga.
Rozkład liczby ujemnej na czynniki pierwsze ma się rozpoczynać od czynnika -1. Twój program powinien
sobie skutecznie poradzić z liczbą -9223372036854775808 oraz 9223372036854775783. Rozkład liczb -1, 0 i 1
ma być tożsamościowy.
Wskazówka.
"
Liczba złożona n posiada co najmniej jeden podzielnik pierwszy, który jest d" n.
1