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()); } }
Wednesday, September 9, 2009
Euler Problem 35 solution
Time (s): ~0.921
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment