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