将完美数字检查优化为 O(sqrt(n))

Question

我的部分程序会检查输入的数字是否为完美数字。我们应该找到一个在 O(sqrt(n)) 中运行的解决方案。我的程序的其余部分在固定时间内运行，但这个功能阻碍了我。

function Perfect(x: integer): boolean;
var
  i: integer;
  sum: integer=0;
begin
  for i := 1 to x-1 do
    if (x mod i = 0) then
      sum := sum + i;
    if sum = x then
      exit(true)
    else
      exit(false);
end;

这在 O(n) 时间内运行，我需要将它减少到 O(sqrt(n)) 时间。

这些是我想出的选项：

(1) 想办法让 for 循环从 1 到 sqrt(x)...

(2) 找到一种不使用 for 循环来检查完全数的方法...

有什么建议吗？我感谢任何提示、技巧、指导等。:)

Answer 1

您需要迭代循环而不是 for i := 1 to x-1，而是 for i := 2 to trunc(sqrt(x))。最高整数除数是 x 但我们在寻找完美数字时没有考虑它。我们改为将总和增加 1（或用 1 初始化它，而不是 0）。

用于此目的的代码if (x mod i = 0) then sum := sum + i;可以转换为：

if (x mod i = 0) then
  begin
    sum := sum + i;
    sum := sum + (x div i);
  end;

于是我们得到以下代码：

function Perfect(x: integer): boolean;
var
  i: integer;
  sum: integer = 1;
  sqrtx: integer;
begin
  sqrtx := trunc(sqrt(x));
  i := 2;
  while i <= sqrtx do
    begin
    if (x mod i = 0) then
      begin
        sum := sum + i;
        sum := sum + (x div i) // you can also compare i and x div i 
                               //to avoid adding the same number twice 
                               //for example when x = 4  both 2 and 4 div 2 will be added
      end;
    inc(i);
    end;
    if sum = x then
      exit(true)
    else
      exit(false);
end;

将完美数字检查优化为 O(sqrt(n))

Optimize a perfect number check to O(sqrt(n))

time

pascal

freepascal

time-complexity

asymptotic-complexity