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