Pages

Wednesday, September 9, 2009

Euler Problem 35 solution

Time (s): ~0.921
package margusmartseppcode.From_30_to_39;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem_35 {
 static boolean contains_024568(final char[] input) {
  int n = input.length;
  for (int i = 4; i < n; i++)
   if (input[i] == '0' || input[i] == '2' || input[i] == '4'
     || input[i] == '5' || input[i] == '6' || input[i] == '8')
    return true;
  return false;
 }

 static void rotate(StringBuilder sb) {
  sb.append(sb.charAt(0)).delete(0, 1);
 }

 static int iRotate(StringBuilder s) {
  return Integer.parseInt(s.append(s.charAt(0)).delete(0, 1).toString());
 }

 static void CircularPrimes(Integer elem, Set<Integer> primes,
   Set<Integer> found, Set<Integer> circular) {
  StringBuilder sb = new StringBuilder("" + elem);
  ArrayList<Integer> tmp = new ArrayList<Integer>();
  int n = sb.length(), i;

  if (found.contains(elem) || circular.contains(elem))
   return;
  for (i = 1; i <= n; i++)
   tmp.add(iRotate(sb));
  for (Integer mem : tmp)
   if (!primes.contains(mem)) {
    found.addAll(tmp);
    return;
   }

  circular.addAll(tmp);
 }

 public static void main(String[] args) throws FileNotFoundException {
  Set<Integer> circular = new HashSet<Integer>();
  Set<Integer> primes = new HashSet<Integer>();
  Set<Integer> found = new HashSet<Integer>();
  Scanner sc = new Scanner(new File("primes1m.txt"));

  for (String tmp = sc.next(); sc.hasNext(); tmp = sc.next())
   if (!contains_024568(tmp.toCharArray()))
    primes.add(Integer.parseInt(tmp));

  for (Integer elem : primes)
   CircularPrimes(elem, primes, found, circular);

  System.out.println(circular.size());
 }
}

No comments:

Post a Comment