patternjavaMinor
Finding the perfect numbers between 1 - 1000
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:
What are some ways that I can improve on this code? More specifically, ways to shorten it.
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:
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).
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.