Reccho - 2 years ago 253

Pascal 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. :)

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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**