: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

R O Z K Ł A D   L I C Z B Y   N A   C Z Y N N I K I   P I E R W S Z E

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Zgodnie ze znaną ze szkoły podstawowej metodą "na kresce" liczbę naturalną dzieli się kolejno przez 2, 3, 4, itd. przy czym dzielenie przez I wykonujemy dopóty, dopóki liczba jest podzielna przez I - ilość wykonanych dzieleń będzie stopniem dzielnika I. Do zapamiętania rozkładu można użyć prostokątnej tablicy o dwóch wierszach i 30 kolumnach. W pierwszym wieszu pamiętane są dzielniki, przez które była dzielona liczba N, od najmniejszego do największego, w wierszu drugim stopnie tych dzielników. Poniższy program wczytuje liczbę całkowitą, wyznacza jej rozkład R na czynniki pierwsze a następnie wypisuje podaną liczbę w postaci iloczynu liczb pierwszych. Rozkład R można wykorzystać do wyznaczenia ilości wszystkich dzielników liczby N.

Type

  Rozklad = Array[1..2, 1..31] Of LongInt;

Function Pierwsza(N : LongInt) : Boolean;
Var
  I : LongInt;
  P : Word;
Begin
 If N<2 Then Pierwsza:=False
 Else
   Begin
     I:=2;
     P:=Round(Sqrt(N));
     While (I<P) And ((N Mod I)<>0) Do Inc(I);
     Pierwsza:=((N Mod I)<>0);
   End;
End;

Var
  R : Rozklad;
  I, J, K, N : LongInt;
 
Begin
  Repeat
    Write(#13#10'N=');
    ReadLn(N);
  Until N>1;
  Write(N, '=');
  For I:=1 To 2 Do
    For J:=1 To 30 Do R[I, J]:=0;

  {Wyznacz rozkład}
  I:=2;
  K:=1;
  While I<=Round(Sqrt(N)) Do
    Begin
      If (N Mod I)=0 Then
        Begin
          While (N Mod I)=0 Do
            Begin
              R[1, K]:=I;
              Inc(R[2, K]);
              N:=N Div I;
            End;
          Inc(K);
        End;
      Inc(I);
    End;

  If N<>1 Then
    Begin
      R[1, K]:=N;
      R[2, K]:=1;
    End;

  K:=1;
  While R[1, K]<>0 Do
    Begin
      For I:=1 To R[2, K] Do
        If (K+I)>2 Then Write('*', R[1, K])
        Else Write(R[1, K]);
      Inc(K);
    End;
  ReadLn;
End.