O（sqrt（n））に完全な数値チェックを最適化する

Question

プログラムの一部入力番号が完全な数であるかどうかをチェックします。私たちは、O（sqrt（n））で実行される解を見つけるはずです。残りのプログラムは一定の時間内に実行されますが、この機能は私を後押ししています。

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; 

これはO（n）時間で実行され、これをO（sqrt（n））時間に減らす必要があります。 （2）検索...

（1）ループ（x）はSQRTに1から行くために作るための方法を見つける

：

これらは私が作ってみたのオプションがありますforループを使用しない完全な数をチェックする方法...

何か提案がありますか？ヒント、ヒント、指導などに感謝します:)

Answer 1

for i := 1 to x-1ではなくfor i := 2 to trunc(sqrt(x))のサイクルを繰り返す必要があります。 最高の整数の除数はxですが、完全な数値を探す際は考慮しません。代わりに、合計を1ずつインクリメントします（または、0ではなく1で初期化します）。

この目的のためにコードif (x mod i = 0) then sum := sum + i;をに変換することができます。整数で（5が知られている）だけ少数完全数があり

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;