HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Finding the perfect numbers between 1 - 1000

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thenumbersperfectbetween1000finding

Problem

This code was made to find all the perfect numbers between 1 and 1000. A perfect number, is a number where all of it's divisors add up to that number.

For example:

6 is divisible by 3,2, and 1 and3+2+1 = 6. Therefore 6 is a perfect number.

public class Perfect {
    public static void main(String[] args) {
        final int LIMIT = 1000;
        boolean isPerfect = false;
        int i;
        for(i = 2; i < LIMIT; i++) { 
            isPerfect = isNumPerfect(i);
            if(isPerfect) {
                System.out.println(i + " is a perfect number");
            }
        }
    }
    public static boolean isNumPerfect(int i) {
        boolean isPerfect = false;
        int sum = 1;
        int x;
        for(x = 2; x <= i / 2; x++) {
            if(i % x == 0) {
                sum += x;
            }
        }
        if(sum == i) {
            isPerfect = true;
        }
        return isPerfect;
    }
}


What are some ways that I can improve on this code? More specifically, ways to shorten it.

Solution

If you're trying to shorten it, there are only 3 perfect numbers up to 1000: just list 6, 28, and 496.

If you're trying to speed it up, an array of 1000 numbers is small enough to stay reasonably cache-resident: you can compute all divisor sums together faster than you can compute each of them one at a time. This is similar to how you can sieve a long interval for primes much faster than you can test each number individually for primality. Code fragment:

for(int i=1; i<=n/2; i++) {
  for(int x=2*i; x<=n; x+=i) {
    divisor_sum[x] += i;
  }
}


The length of the inner loop is O(n/i), which gets small very quickly, making the total cost O(n log n), whereas your double loop is O(n^2).

Code Snippets

for(int i=1; i<=n/2; i++) {
  for(int x=2*i; x<=n; x+=i) {
    divisor_sum[x] += i;
  }
}

Context

StackExchange Code Review Q#114587, answer score: 4

Revisions (0)

No revisions yet.