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)) 시간까지 줄여야합니다.

이

(1) for 루프는 SQRT (x)는 1에서 갈 수 있도록하는 방법을 찾기 ...

(2)을 (를) 찾기 :

이 내가 가지고 올 한 옵션은 방법에 대한 루프를 사용하지 않는 완벽한 번호를 확인하는 방법 ...

어떤 제안? 어떤 힌트, 팁, 지시 등을 주셔서 감사합니다.

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;는로 변환 할 수 있습니다 :

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

그래서 우리는 다음과 같은 코드를 얻을 : 오직 정수에 (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;