PROSAGA码农传奇-pascal-将完美数字检查优化为O（sqrt（n））

将完美数字检查优化为O（sqrt（n））

作者: 咿呀哟
发布时间: 2024-04-18 01:17:53 (11小时前)
转自：

<div class =“post-text”itemprop =“text”>
  <P>
    你不需要迭代循环
     <code>
      for i := 1 to x-1
    </code>
     但
     <code>
      for i := 2 to trunc(sqrt(x))
    </code>
    。
最高整数除数是
     <code>
      x
    </code>
     但是在寻找完美的数字时我们不会考虑它。我们将sum加1（或者用1初始化 - 而不是0）。
  </p>
  <P>
    代码
     <code>
      if (x mod i = 0) then sum := sum + i;
    </code>
     为此目的可以转换为：
  </p>
   <pre>
    <code>
      if (x mod i = 0) then
  begin
    sum := sum + i;
    sum := sum + (x div i);
  end;

</code>
  </pre>
  <P>
    所以我们得到以下代码：
  </p>
   <pre>
    <code>
      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;

</code>
  </pre>
</DIV>