obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Rozwiązywanie arkuszy maturalnych z informatyki

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).

Poziom podstawowy

Zadanie 2. Rozkład liczby (7 pkt)

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:

obrazek

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.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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