Problem specification: ProjectEuler.net Problem 23
To find if a number is abundant we must sum its proper divisors. .
The quotient of each division by a proper divisor is also a proper divisor of the dividend. This fact is exploited to minimise the number of calculations required to ascertain whether a number is abundant or not.
Once we have the abundant numbers, the solution is trivial.
Execution time: 450ms (laptop)
CODE
import java.util.ArrayList;
/**
* Project euler problem 23 java solution
* Abundants
* @author Mike
*/
public class Problem_23 {
public static void main(String[] args){
// create a collection of abundant numbers
ArrayList
for(int i = 1; i <= 28123; i++){
int j = divisors(i);
if(j > i){
abundants.add(i);
}
}
int[] array = new int[28123];
int len = array.length;
for(int i = 0; i < len; i++){
array[i] = i + 1;
}
// now we have all abundants.
Iterator
while(it.hasNext()){
int one = it.next();
for(int j = 0; j < abundants.size(); j++){
int sum = one + abundants.get(j);
if(sum <= len){
array[sum - 1] = 0;
}
}
it.remove();//remove it as checked against ALL numbers
}
int sum = 0;
len = array.length;
for(int i = 0; i < len; i++){
sum += array[i];
}
System.out.println(sum);
}
/**
* Returns the sum of the divisors of a number.
* @param number
* @return
*/
public static int divisors(int number){
int d = (int) Math.sqrt(number) + 1;
int sum = 1;
for(int i = 2; i < d; i++){
if(number % i == 0){
sum += i;
if(i != (number / i)){
sum += (number / i);
}
}
}
return sum;
}
}
Any suggestions and comments are welcome, please send me an email (see contacts).