Optimieren Sie eine Überprüfung der perfekten Nummer auf O (sqrt (n))

Question

Teil des Programms Ich habe überprüft, ob eine Eingabe-Nummer eine perfekte Nummer ist. Wir sollen eine Lösung finden, die in O (sqrt (n)) läuft. Der Rest meines Programms läuft in konstanter Zeit, aber diese Funktion hält mich zurück.

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; 

Dies läuft in O (n) Zeit, und ich brauche es auf O (sqrt (n)) Zeit zu verkürzen.

Dies sind die Optionen, die ich gekommen bin oben mit:

(1) Finden Sie einen Weg für die Schleife von 1 bis sqrt (x) gehen zu machen ...

(2) finden Möglichkeit, nach einer perfekten Nummer zu suchen, die keine For-Schleife verwendet ...

Irgendwelche Vorschläge? Ich schätze alle Hinweise, Tipps, Anweisungen usw. :)

Answer 1

Sie müssen den Zyklus nicht for i := 1 to x-1 aber for i := 2 to trunc(sqrt(x)) iterieren. Der höchste ganzzahlige Divisor ist x, aber wir berücksichtigen dies nicht, wenn wir nach perfekten Zahlen suchen. Wir erhöhen die Summe um 1 (oder initialisieren sie mit 1 - nicht 0).

Der Code if (x mod i = 0) then sum := sum + i; für diesen Zweck können umgewandelt werden:

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

Und so erhalten wir den folgenden 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;