Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2010 mgr
Jerzy Wałaszek |
Z podanych rozwiązań należy korzystać dopiero po samodzielnym rozwiązaniu danego zadania w celu sprawdzenia poprawności wyniku. Rozwiązania nie są optymalne (nie zostały sprawdzone z kluczem odpowiedzi, ponieważ na dzień dzisiejszy klucz ten nie został jeszcze opublikowany w Internecie).
Rozkładem na czynniki pierwsze liczby całkowitej większej od 1 nazywamy przedstawienie tej liczby w postaci iloczynu czynników pierwszych (liczb pierwszych). Jeżeli dana liczba jest liczbą pierwszą, to w jej rozkładzie występuje tylko ona sama.
Przykłady:
24 = 2 × 2 × 2 × 3
20 = 2 × 2 × 5
19 = 19
Podaj rozkład na czynniki pierwsze następujących liczb całkowitych:
Liczba | Rozkład na czynniki pierwsze |
63 | 3 3 7 |
184 | 2 2 2 23 |
277 | 277 |
Ułóż algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku programowania), który dla liczby całkowitej n (n > 1) podaje wszystkie jej czynniki pierwsze występujące w rozkładzie.
Specyfikacja
Dane: liczba całkowita n (n > 1)
Wynik: wszystkie czynniki pierwsze liczby n
Przykłady:
Dla n = 24 poprawnym wynikiem jest 2, 2, 2, 3.
Dla n =19 poprawnym wynikiem jest 19.
Istnieje kilka algorytmów rozkładu na czynniki pierwsze. Na maturze można podać najprostszy z nich, zwany bezpośrednim poszukiwaniem rozkładu na czynniki pierwsze (ang. direct search factorization lub trial division). W algorytmie tym sprawdza się podzielność liczby n przez kolejne liczby naturalne i od 2 do pierwiastka z n. Jeśli liczba n jest podzielna przez daną liczbę i, to liczbę i wyprowadzimy na wyjście, a za nowe n przyjmiemy wynik dzielenia i próbę dzielenia będziemy powtarzać dotąd, aż nie będzie to już możliwe. Wtedy przejdziemy do następnego dzielnika. Gdy wykorzystamy wszystkie dzielniki, musimy sprawdzić, czy liczba n została zredukowana do 1. Jeśli nie, to jest ona równa ostatniemu dzielnikowi, który jest większy od wyliczonego wcześniej pierwiastka z n. Więcej informacji na ten temat znajdziesz tu:
Rozkład
na czynniki pierwsze metodą próbnych dzieleń
Rozkład na czynniki
pierwsze metodą Fermata
Lista kroków:
krok 1: g ← [√n]
krok 2: i ← 2
krok 3: Jeśli i > g, to idź do kroku 7
krok 4: Dopóki n mod i = 0, to
wykonuj:
Pisz i
n ← n / i
krok 5: i ← i + 1
krok 6: Idź do kroku 3
krok 7: Jeśli n > 1, to pisz n
krok 8: Zakończ
Schemat blokowy:
Program C++:
// Zadanie 2b // Rozkład na czynniki pierwsze //----------------------------- #include <iostream> #include <cmath> using namespace std; int main() { unsigned g,i,n; cin >> n; g = sqrt(n); for(i = 2; i <= g; i++) while(n % i == 0) { cout << i << " "; n /= i; } if(n > 1) cout << n; cout << endl; return 0; } |
Program Pascal:
{ Zadanie 2b Rozkład na czynniki pierwsze ----------------------------} program rozklad; var g,i,n : cardinal; begin readln(n); g := round(sqrt(n)); for i := 2 to g do while n mod i = 0 do begin write(i,' '); n := n div i; end; if n > 1 then write(n); writeln; end. |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe