 Reccho - 2 years ago 253
Pascal Question

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

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. :) asd-tm

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;
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download