Florian Florian - 1 month ago 23
Pascal Question

Prime factorization in pascal as a function/procedure

I have to build a prime factorization program with pascal using a function or procedure.
I think I am on a pretty good path, but my problem at the moment is, that it seems to be impossible to assign a dynamic relay as the ouput of a function/procedure. And I have no real clue what I could use or do instead (except a string, but that feels just not right at all).

PROCEDURE PrimFac(n: INTEGER; VAR res: array of INTEGER);

VAR
divisor, a, counter: INTEGER;
b: array of INTEGER;

BEGIN
divisor := 2;
a := n;
counter := 0;
WHILE divisor <= n DIV 2 DO BEGIN
IF a MOD divisor = 0 THEN BEGIN
a := a DIV divisor;
counter := counter + 1;
SetLength(b, counter);
b[counter] := divisor;
END
ELSE
divisor := divisor + 1;
END;
res := b
END;

BEGIN
WriteLn(PrimFac(210));
END.


Any help or hint would be highly appreciated. (:
Thank you very much in advance
-Florian

Answer

I see this is FreePascal, which is quite similar to Delphi.

Instead of using an open array parameter (which should not be confused with a dynamic array, despite the similar syntax), you should pre-define a type to return:

type
  TIntegerDynArray = array of Integer;

function PrimFac(n: Integer): TIntegerDynArray;
...
  SetLength(Result, counter);
  Result[counter - 1] := divisor;
...

FWIW, reallocating a dynamic array each time you want to add an element is generally not a good idea. Better to keep the results in a temporary TList (if possible, a generic TList) and then, at the end, to turn that into an array of the desired length, and then to get rid of the temporary list again, IOW something like (untested):

uses
  fgl;

type
  TIntegerDynArray = array of Integer;
  TIntegerList = specialize TFPGList<Integer>;

function PrimFac(N: Integer): TIntegerDynArray;
var
  Divisor, A, I: Integer;
  L: TIntegerList; 
begin
  A := N;
  L := TIntegerList.Create;
  try
    { Find divisors and add each to list. }
    for Divisor := 2 to N div 2 do
    begin
      { Use "while" so a divisor can be found multiple times, e.g. }
      { using "if": 1000 --> 2 4 5 25 (but 4 = 2*2, and 25 = 5*5)  }
      { using "while": 1000 --> 2 2 2 5 5 5                        }
      while A mod Divisor = 0 do
      begin
        A := A div Divisor;
        L.Add(Divisor);
      end;
    end;

    { Copy list to result array. }
    SetLength(Result, L.Count);
    for I := 0 to L.Count - 1 do
    begin
      Result[I] := L[I];
    end;
  finally
    L.Free;
  end;
end;

Note that your algorithm could do with a few extra checks (for 0, for 1, etc.), but that is up to you. I merely answered how to return the values.

Update

If you want to print the list, then do something like:

    { Find divisors and print each one. }
    for Divisor := 2 to N div 2 do
    begin
      while A mod Divisor = 0 do
      begin
        A := A div Divisor;
        L.Add(Divisor);
        Write(Divisor, ' ');
      end;
    end;
    Writeln;

This lists all numbers separated by spaces and performs a final newline when it is finished. If you want more sophisticated output, use your imagination.