Perfect Number


  • 0

    Click here to see the full article post


  • 0
    Z

    int sum = 1;
    for (int i = 2; i * i < num; i++) {
    if (num % i == 0)
    sum += i + num / i;
    }
    double n = Math.sqrt(num);
    if (Math.floor(n) == n) sum += n;
    return sum == num;


  • 0
    R

    One quick optimization: https://en.wikipedia.org/wiki/Perfect_number
    Since all known perfect numbers are of the form
    N= 2^(p−1) * ((2^p − 1)) is an even perfect number whenever 2^p − 1 is prime (Mersenne primes)
    (which can only happen when p is prime also).

    The only valid values of p which can be used to make Perfect numbers that fit in 64-bits is:
    p = 2, 3, 5, 7, 13, 17, 19, 31


  • 0
    S

    You can have two nested for loops, and without "intelligently" understanding that you have to loop up to sqrt(num), you can drop out of the loop if the sum of the devisors is becoming larger than num. This is a slightly more efficient brute force suggested.

    unsigned sum = 0;
    for (int i = 0; i < num; i++)
    {
       if (0 == (num%i))
          {
             sum += i;
             if (sum > num)
             {
                return false;
             }
          }
    }
    if (sum == num)
    {
        return true;
    }
    return false;

  • 0

    @sanabani I will add this approach soon. Thanks


  • 0
    S

    Approach #3 Better Brute Force but [Accepted] ;)

    bool checkPerfectNumber(int num) {
            if (num <= 1) {
                return false;
            }
            int sum = 1;
            int maxNum = num;
            for (int i = 2; i < maxNum; i++) {
                if (num % i == 0) {
                    maxNum = num / i;
                    sum += i;
                    sum += maxNum;
                }
                if (sum > num) {
                    break;
                }
            }
            return sum == num;
        }
    

  • 0
    S

    public boolean checkPerfectNumber(int num) {
    if (num==1) return false;
    int sum=1;
    int xn = num;
    for (int i=2; i<xn; i++) {
    if (num%i==0) {
    xn = num/i;
    sum = sum + i + xn;
    }
    }

    return (sum==num);
    }


  • 0
    N

    You could simply start with sum as 1; start from i=2 and avoid the last substraction.

       public static boolean checkPerfectNumber(int num) {
            if (num == 1) {
                return false;
            }
            int sum = 1;
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    sum = sum + i;
                    if (i * i != num) {
                        sum = sum + (num / i);
                    }
                }
            }
            System.out.println(sum);
            return sum == num;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.