Разложить заданное натуральное число на простые множители

type
  tSpis = ^rSpis;
  rSpis = record
    N, K : Integer;
    Next : tSpis;
  end;
  
var
  N0, N, D : Integer;
  First, Last, Cur : tSpis;
  
procedure AddSpis(N : Integer);
begin
  Cur := First;
  while (Cur <> nil) and (Cur^.N <> N) do
    Cur := Cur^.Next;
  if Cur = nil then
    begin
      New(Cur);
      Cur^.N := N;
      Cur^.K := 1;
      Cur^.Next := nil;
      if First = nil then
        First := Cur
      else
        Last^.Next := Cur;
      Last := Cur;
    end
  else
    Inc(Cur^.K);
end;
 
procedure OutSpis;
begin
  Cur := First;
  repeat
    Write(Cur^.N);
    if Cur^.K > 1 then Write('^', Cur^.K);
    Cur := Cur^.Next;
    if Cur <> nil then Write(' x ');
  until Cur = nil;
end;
 
begin
  Write('Введите N = '); ReadLn(N0);
  N := N0;
  First := nil;
  
  while not Odd(N) do
    begin
      AddSpis(2);
      N := N shr 1;
    end;
  
  D := 3;
  while D*D < N do
    if N mod D = 0 then
      begin
        AddSpis(D);
        N := N div D;
      end
    else
      Inc(D, 2);
  
  if D*D > N then
    AddSpis(N);
    
  if First <> Last then
    begin
      Write('Число ', N0, ' можно разложить на простые множители: ');
      OutSpis;
      WriteLn;
    end
  else
    WriteLn('Число ', N0, ' простое.');
end.