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

@Phoenix97 · Регистрация: 30.06.2013

Студворк — интернет-сервис помощи студентам

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

Не по теме:

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

Однако, по какой-то причине данный алгоритм выводит неправильные данные (к примеру, для числа 12 программа даёт в ответе 22, хотя правильно 28).
Есть ли идеи, что тут было скоммунизжено не так? Поскольку на С++ алгоритм вроде работает верно.

Pascal

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.

@Joy · 03.04.2016, 04:27

Pascal

var
 sum:uint64=1;
 k:uint64=1;
 i,p,a:uint64;
begin
  readln(a);
  if a=1 then begin writeln(a); exit;end;
   while a and 1 = 0 do begin
      k:=k shl 1;
      a:=a shr 1;
    end;
   k := k shl 1 - 1;
   if a = 1 then begin writeln(k);exit;end
   else  sum:=k;
   i:=3;
   repeat
      p:=1; k:=1;
      while a mod i = 0 do begin
         k *= i;
         p += k;
         a:=a div i;
      end;
      if k > 1 then sum *= p;
   if a > 1 then sum *= a + 1;
   i:=i+2;
   until i*i>a; 
   writeln(sum);
end.

Добавлено через 2 минуты
Phoenix97, я брал последний код из указанной темы. Прошу прощения, что на PABC.NET, FPC на планшете нет

@a1d4r · 03.04.2016, 10:00

38 строка:

Pascal

1	if x > 1 then sum:= sum * (x + 1);

@Phoenix97 · 03.04.2016, 12:52 **[ТС]**

Сообщение от a1d4r

if x > 1 then sum:= sum * (x + 1);

И точно

Не заметил этот косяк. Теперь работает отлично, спасибо!

@bormant · 03.04.2016, 22:11

Ежели что, переписал бы так:

Pascal

{$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.

Добавлено через 10 минут
А это второй:

Pascal

{$mode ObjFPC}
function SumDvsr(a: Int64): Int64;
var i, p: 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; p:=1;
    while a mod i=0 do begin
      p:=p*i; Inc(Result,p); a:=a div i;
    end;
    if p>1 then Result:=Result*p;
    Inc(i,2);
  end;
  if a>1 then Result:=Result*(a+1);
end;
begin
  WriteLn(SumDvsr(12));
end.

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

Решение

Решение

@Phoenix97 0 / 0 / 0 Регистрация: 30.06.2013 Сообщений: 29
	03.04.2016, 12:52 [ТС]	4
	Сообщение от a1d4r if x > 1 then sum:= sum * (x + 1); И точно Не заметил этот косяк. Теперь работает отлично, спасибо! 0

	03.04.2016, 22:11

Опции темы