Разложить число ** простые числа Например 20 = 2^2 + 5^1 Желательно с оптимизацией, чтоб...

Question

Разложить число на простые числа
Например 20 = 2^2 + 5^1
Желательно с оптимизацией, чтоб для 6-значных чисел не считалось пол часа
Программу можно писать на любом языке из C-подобных, Ruby, Pascal, VB и тп

Comments

Какой предел для максимального значения числа, предназначенного для факторизации?

---

Ответ нет, будем считать, что длина чисел типа четырехбайтного целого.

---

чем дольше тем лучше, в идеале нужно чтоб вместилось 43! = 60415263063373835637355132068513997507264512000000000

---

Такой идеал в школьном сервисе искать бесполезно: на него не рассчитаны типы данных, которые используются в базовых языках программирования.

---

на руби у меня вполне получается, остальные не знаю

Answer 1

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 n<>1 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