完全数 — Leetcode 507

元の問題リンク:https://leetcode.com/problems/perfect-number/

この問題では、与えられた整数 n が完全数であるかどうかを判断するよう求められます。完全数は、そのすべての正の約数 (n 自体を除く) の合計に等しい整数として定義されます。

これを行う最も直感的な方法は、2 から n / 2 までずっとループし、実行中の合計を追跡することです。ただし、当然のことながら、これにより、多数の場合に制限時間超過の例外が発生します。

数学的には、因子を見つけると、それに対応する別の因子が常に存在し、合計の一部になる必要があるためです (たとえば、n = 28 で 2 から開始する場合、28 / 2 = 14 も要因である必要があり、ギャップをより迅速に閉じることができるため、この方法でループの数を半分に減らすことができます)。これは私が思いついた受け入れられた解決策です:

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) {
            return false;
        }
        int sum = 1;
        int left = 2;
        int right = num / 2;
        while (left < right) {
            if (num % left == 0) {
                sum += left;
                sum += (num / left);
                right = num / left;
            }
            left++;
        }
        return sum == num;
    }
}