Pages

Tuesday, September 8, 2009

Euler Problem 7 solution

Time (s): ~0.011
package margusmartseppcode.From_1_to_9;

import java.util.BitSet;

public class Problem_7 {
 static long getSoExnt(int max, int nr) {
  if (max < 1 || nr < 1 || max < nr)
   return -1;
  if (nr < 4)
   return (nr == 1 ? 2 : (nr == 2 ? 3 : 5));
  BitSet sieve = new BitSet(max / 2);

  for (int i = 5, f = 1, c = 2; 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);
    if (++c >= nr)
     return i;
   }

  return -1;
 }

 public static void main(String[] args) {
  System.out.println(getSoExnt(120000, 10001));
 }
} 

No comments:

Post a Comment