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

Question

Part of the program I have checks if an input number is a perfect number. We're supposed to find a solution that runs in O(sqrt(n)). The rest of my program runs in constant time, but this function is holding me back.

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;

This runs in O(n) time, and I need to cut it down to O(sqrt(n)) time.

These are the options I've come up with:

(1) Find a way to make the for loop go from 1 to sqrt(x)...

(2) Find a way to check for a perfect number that doesn't use a for loop...

Any suggestions? I appreciate any hints, tips, instruction, etc. :)

Answer 1

You need to iterate the cycle not for i := 1 to x-1 but for i := 2 to trunc(sqrt(x)). The highest integer divisor is x but we do not take it in into account when looking for perfect numbers. We increment sum by 1 instead (or initialize it with 1 - not 0).

The code if (x mod i = 0) then sum := sum + i; for this purpose can be converted to:

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

And so we get the following 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;