Pages

Tuesday, September 8, 2009

Euler Problem 10 solution

Time (s): ~0.097
package margusmartseppcode.From_10_to_19;

import java.util.BitSet;

public class Problem_10 {
 /** Sieve of Eratosthenes sum */
 static long getSoEsum(int max) {
  if (max < 1)
   return 0;
  BitSet sieve = new BitSet(max / 2);
  long sum = (max > 1 ? 2 + (max > 2 ? 3 : 0) : 0);

  for (int i = 5, f = 1; i <= max; i += 3 - f, f = -f)
   if (sieve.get(i >> 1) == false) {
    int add = i << 1;
    for (int j = i + add; j < max; j += add)
     sieve.set(j >> 1, true);
    sum += i;
   }

  return sum;
 }

 public static void main(String[] args) {
  System.out.println(getSoEsum(2000000));
 }
}

No comments:

Post a Comment