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

Например 20 = 2^2 + 5^1

Желательно с оптимизацией, чтоб для 6-значных чисел не считалось пол часа

Программу можно писать на любом языке из C-подобных, Ruby, Pascal, VB и тп

Var

i, k, n, p:longint;

f:array[1 ... 10,1 ... 2] of longint;

begin

p:=2; i:=1;

f[1,1]:=1; f[1,2]:=1;

Write ('Введите натуральное число не больше 2 147 483 647: ') ;

Read (n) ;

Write (n,' = 1') ;

while n1 do begin

if (n mod p) = 0 then begin

if f[i, 1]p then

begin Inc (i) ; f[i, 1]:=p; f[i, 2]:=1 end

else Inc (f[i, 2]) ;

n:=n div p

end

else inc (p)

end;

k:=i;

for i:=2 to k do

begin

Write (' x ', f[i, 1]) ;

if f[i, 2]>1 then Write ('^', f[i, 2])

end;

Writeln

end.

Тестовое решение:

Введите натуральное число не больше 2 147 483 647: 223092870

223092870 = 1 x 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23

Введите натуральное число не больше 2 147 483 647: 65536

65536 = 1 x 2^16

Введите натуральное число не больше 2 147 483 647: 2147483647

2147483647 = 1 x 2147483647