package margusmartseppcode.From_30_to_39; import java.io.File; import java.io.FileNotFoundException; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Problem_37 { static Integer cint(String nr) { return Integer.parseInt(nr); } static boolean isLTP(String mem, Set<Integer> primes) { int n = mem.length(); if (n < 1) return true; return primes.contains(cint(mem)) && isLTP(mem.substring(1), primes); } static boolean isRTP(String mem, Set<Integer> primes) { int n = mem.length(); if (n < 1) return true; return primes.contains(cint(mem)) && isRTP(mem.substring(0, n - 1), primes); } static boolean isTP(String mem, Set<Integer> primes) { return isLTP(mem, primes) && isRTP(mem, primes); } private static void bTP(Integer mem, Set<Integer> primes, Set<Integer> truncatable) { if (primes.contains(mem)) { if (isTP(""+mem, primes)) truncatable.add(mem); TruncatablePrimes(mem, primes, truncatable); } } private static void TruncatablePrimes(Integer elem, Set<Integer> primes, Set<Integer> truncatable) { String[] o = new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9" }; String s = "" + elem; for (String pos : o) { bTP(cint(s + pos), primes, truncatable); bTP(cint(pos + s), primes, truncatable); } } public static void main(String[] args) throws FileNotFoundException { Set<Integer> truncatable = new HashSet<Integer>(); Set<Integer> primes = new HashSet<Integer>(); Scanner sc = new Scanner(new File("primes1m.txt")); int sum = 0; for (String tmp = sc.next(); sc.hasNext(); tmp = sc.next()) primes.add(Integer.parseInt(tmp)); for (Integer elem : new Integer[] { 3, 7 }) TruncatablePrimes(elem, primes, truncatable); for (Integer elem : truncatable) sum += elem; System.out.println(sum); } }
Wednesday, September 9, 2009
Euler Problem 37 solution
Time (s): ~0.599
Labels:
Euler Problem 30-39,
File,
HashSet,
prime numbers,
Scanner,
truncatable
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment