Быстрый алгоритм нахождения суммы делителей натурального числа - Free Pascal

Узнай цену своей работы

Формулировка задачи:

Собственно, тема является идейным продолжением реализации этого алгоритма на С++ (Быстрое нахождение количества делителей натурального числа).

Не по теме:

А точнее, наглым образом переписанный на Паскаль алгоритм из этой темы

Однако, по какой-то причине данный алгоритм выводит неправильные данные (к примеру, для числа 12 программа даёт в ответе 22, хотя правильно 28). Есть ли идеи, что тут было скоммунизжено не так? Поскольку на С++ алгоритм вроде работает верно.
var
  sum : Int64;
  i, x, k : integer;
 
begin
  read(x);
  if x = 1 then 
  begin
    write(1);
    Halt;
  end;
  sum:= 1;
  k:= 1;
  while (x and 1) = 0 do 
  begin
    k:= k shl 1;
    x:= x shr 1;
  end;
  k:= (k shl 1) - 1;
  if x = 1 then 
  begin
    write(k);
    Halt;
  end 
  else sum:= k;
  i:= 3;
  while (i*i) <= x do 
  begin
    k:= 1;
    while x mod i = 0 do 
    begin
      k:= k * i;
      x:= x div i;
    end;
    if k > 1 then sum:= sum * ((k*i - 1) div (i - 1));
    i:= i + 2;
  end;
  if x > 1 then sum:= sum * x + 1;
  write(sum);
end.

Решение задачи: «Быстрый алгоритм нахождения суммы делителей натурального числа»

textual
Листинг программы
{$mode ObjFPC}
function SumDvsr(a: Int64): Int64;
var i: Longint;
begin
  Result:=1; if a=1 then Exit;
  while a and 1=0 do begin
    Result:=Result shl 1; a:=a shr 1;
  end;
  Result:=Result shl 1-1;
  if a=1 then Exit;
  i:=3;
  while sqr(i)<=a do begin
    Result:=1;
    while a mod i=0 do begin
      Result:=Result*i; a:=a div i;
    end;
    if Result>1 then Result:=(Result*i-1) div (i-1);
    Inc(i,2);
  end;
  if a>1 then Result:=Result*(a+1);
end;
begin
  WriteLn(SumDvsr(12));
end.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4.6 из 5
Похожие ответы