% Primfaktorzerlegung(Z) : Z wird in seine Primfaktoren zerlegt.
% Eine Matrix 'Prim' die in der ersten Zeile die Primzahlen und in der
% zweiten deren Anzahl enthält, sowie die Anzahl der durchgeführten Tests
% wird ausgegeben.

% #########################################################################
% CoMa I -  2. Übung zur Vorlesung
% Abgabe: 06.11.08
% Autoren:
%   Matthias Bosewitz
%   Alexander Fritz
% Aufgabe 1:
% Zahlen in Primfaktoren zerlegen
% Wir verwenden eine Funktion, die wir in dieser Einzeldatei belassen damit
% wir diese Primfaktorzerlegung auch später immer wieder aufrufen können
% ohne den Code dafür anpassen zu müssen.
% #########################################################################


function [Prim,Tests] = Primfaktorzerlegung(Z)

% Z = 1 führt zum Ergebnis Prim = [0 ; 0] und Tests = 1 !

Prim  = [0 ; 0];        % Liste mit den Primfaktoren (Zeile 1)
                        % und deren Anzahl (Zeile 2)
T     = 3;              % Zu prüfender Teiler (nicht immer Prim)
Index = 0;              % Index (Spalte) der Primzahl in 'Prim'

Tests = 1;              % Anzahl der Teilbarkeitstests (min. 1x)

if mod(Z,2) == 0        % Wenn Z durch 2 teilbar
    Prim(1,1) = 2;      % Primzahl 2 hinzufügen
    Index = 1;          % Erste Primzahl ist 2, nächste kann erst in
                        % Spalte 2 gespeichert werden
    while mod(Z,2) == 0     % Weitere Teilbarkeit durch 2 testen
        Z = Z / 2;          % Zahl durch 2 teilen
        Tests = Tests + 1;  % Weiterer Teilbarkeitstest durchgeführt
        Prim(2,1) = Prim(2,1)+1;  % Vorkommen des Primfaktors plus 1
    end
end

while Z ~= 1                % Solange bis Z völlig zerlegt ist
    
    Tests = Tests + 1;      % mindestens 1x wird getestet
    if mod(Z,T) == 0        % Wenn Z durch T teilbar ist
        Index = Index + 1;    % Nächste Spalte wählen
        Prim(1,Index) = T;    % T (ist Primzahl) hinzufügen
        while mod(Z,T) == 0     % Solange die Zahl durch T teilbar ist
            Z = Z / T;          % Zahl durch 2 teilen
            Tests = Tests + 1;  % Weiterer Teilbarkeitstest durchgeführt
            Prim(2,Index) = Prim(2,Index)+1;   % Vorkommen Primfaktor + 1
        end
    end
    T = T+2;             % Nächstes T ausprobieren
                         % (nur ungerade kommen als Primzahlen in Frage)    
end

end