Pages

Tuesday, September 8, 2009

Euler Problem 23 solution

Time (s): ~0.231
package margusmartseppcode.From_20_to_29;

public class Problem_23 {
 public static boolean IsAbundant(int num) {
  int factorSum = 1;
  double temp = Math.sqrt(num);

  if (temp % 1 == 0)
   factorSum -= temp;
  for (int i = 2; i <= temp; i++)
   if (num % i == 0)
    factorSum += i + num / i;

  if (factorSum > num)
   return true;

  return false;
 }

 public static void main(String[] args) {
  final int size = 28123;
  int[] d = new int[8192];
  int[] not = new int[size];
  int c = 0, c2 = 0, sum = 0;

  for (int i = 10; i <= size; i++)
   if (IsAbundant(i))
    d[c++] = i;

  for (int i = 0; i < c; i++)
   for (int j = i; j < c; j++)
    if ((c2 = d[i] + d[j]) < size)
     not[c2] = 1;

  for (int i = 1; i < size; i++)
   if (not[i] != 1)
    sum += i;

  System.out.println(sum);
 }
}

No comments:

Post a Comment