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

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

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

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

Не по теме:

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

Однако, по какой-то причине данный алгоритм выводит неправильные данные (к примеру, для числа 12 программа даёт в ответе 22, хотя правильно 28). Есть ли идеи, что тут было скоммунизжено не так? Поскольку на С++ алгоритм вроде работает верно.
Листинг программы
  1. var
  2. sum : Int64;
  3. i, x, k : integer;
  4. begin
  5. read(x);
  6. if x = 1 then
  7. begin
  8. write(1);
  9. Halt;
  10. end;
  11. sum:= 1;
  12. k:= 1;
  13. while (x and 1) = 0 do
  14. begin
  15. k:= k shl 1;
  16. x:= x shr 1;
  17. end;
  18. k:= (k shl 1) - 1;
  19. if x = 1 then
  20. begin
  21. write(k);
  22. Halt;
  23. end
  24. else sum:= k;
  25. i:= 3;
  26. while (i*i) <= x do
  27. begin
  28. k:= 1;
  29. while x mod i = 0 do
  30. begin
  31. k:= k * i;
  32. x:= x div i;
  33. end;
  34. if k > 1 then sum:= sum * ((k*i - 1) div (i - 1));
  35. i:= i + 2;
  36. end;
  37. if x > 1 then sum:= sum * x + 1;
  38. write(sum);
  39. end.

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

textual
Листинг программы
  1. {$mode ObjFPC}
  2. function SumDvsr(a: Int64): Int64;
  3. var i: Longint;
  4. begin
  5.   Result:=1; if a=1 then Exit;
  6.   while a and 1=0 do begin
  7.     Result:=Result shl 1; a:=a shr 1;
  8.   end;
  9.   Result:=Result shl 1-1;
  10.   if a=1 then Exit;
  11.   i:=3;
  12.   while sqr(i)<=a do begin
  13.     Result:=1;
  14.     while a mod i=0 do begin
  15.       Result:=Result*i; a:=a div i;
  16.     end;
  17.     if Result>1 then Result:=(Result*i-1) div (i-1);
  18.     Inc(i,2);
  19.   end;
  20.   if a>1 then Result:=Result*(a+1);
  21. end;
  22. begin
  23.   WriteLn(SumDvsr(12));
  24. end.

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


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

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

5   голосов , оценка 4.6 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы