// Solution to "Prime Sequences" by Bob Roos // // Basic idea: just plain old backtracking. Precompute a list of all // primes between 1 and 2000 to avoid repeated primality tests, then, for // each integer i between n and m, compute a list of all other integers j // in that range such that i+j is prime; iterate over these lists during // backtracking. import java.io.*; import java.util.*; public class AntiPrime { public static BufferedReader in; public static int n,m; // lower and upper bounds of prime sequence public static int d; // max in-a-row sums public static final int MAX = 10001; // since n,m are <= 1000 and d <= 10 public static boolean isPrime[] = new boolean[MAX]; // true iff prime public static Vector possibleNbr[]; // possibleNbr[i-n] = {j: isPrime[i-n+j]} public static boolean used[]; // check off each number as it is used public static int path[]; // solution = final list of numbers ///////////////////////////////////////////////////////////////// // main -- loops over the input instances: public static void main(String[] args) throws IOException { // Precompute primality for all integers of interest: initPrimes(); in = new BufferedReader(new InputStreamReader(System.in)); // Get first instance: String line = in.readLine().trim(); StringTokenizer tok = new StringTokenizer(line); n = Integer.parseInt(tok.nextToken()); m = Integer.parseInt(tok.nextToken()); d = Integer.parseInt(tok.nextToken()); // Loop over instances: while (n > 0 && m > 0) { process(); // Get next instance: line = in.readLine().trim(); tok = new StringTokenizer(line); n = Integer.parseInt(tok.nextToken()); m = Integer.parseInt(tok.nextToken()); d = Integer.parseInt(tok.nextToken()); } } ///////////////////////////////////////////////////////////////// // All the work is done here: public static void process() { int size = m-n+1; // number of values in the range possibleNbr = new Vector[size]; // for each i, find all j s.t. isPrime[i+j] // Initialize neighbor lists to empty vectors: for (int i = 0; i < size; i++) { possibleNbr[i] = new Vector(); } // Fill in the "possible neighbors" list: for (int i = 0; i < size; i++) { for (int j = i+1; j < size; j++) { if (!isPrime[n+i+n+j]) { possibleNbr[i].add(new Integer(n+j)); possibleNbr[j].add(new Integer(n+i)); } } } /* DEBUG: System.out.println("Prime sums:"); for (int i = 0; i < size; i++) { System.out.print((i+n)+"+: "); for (int j = 0; j < possibleNbr[i].size(); j++) { System.out.print(possibleNbr[i].get(j)+" "); } System.out.println(); } */ // Initialize the solution array: path = new int[size]; // Initialize the "used" array (initially no numbers have been used): used = new boolean[size]; for (int i = 0; i < size; i++) used[i] = false; // Finally! Enumerate all possible starting values for the sequence // and recursively try to complete them (we are essentially computing // a Hamiltonian path through a graph whose vertices are integers // connected by edges when their sum is prime): for (int k = n; k <= m; k++) { // See if this is a solution; if so, print and return: if (hamPath(k,0)) { for (int i = 0; i < size; i++) { if (i > 0) System.out.print(","); System.out.print(path[i]); } System.out.println(); return; } } // No Hamiltonian path found, so give up: System.out.println("No anti-prime sequence exists."); } ///////////////////////////////////////////////////////////////// // Recursively try to extend the Hamiltonian path in "path" starting // from vertex "i"; success if we reach "count": public static boolean hamPath(int i, int count) { //System.out.println("DEBUG -- hamPath: i = " + i + ", count = " + count); int size = m-n+1; // See if all sums are non-prime: int sum = i; boolean ok = true; int r = count-1; while (r >= 0 && r > count-d) { sum += path[r]; if (isPrime[sum]) { //System.out.print("Rejecting "); //for (int z = 0; z < count; z++) // System.out.print(path[z]+","); //System.out.println(i); //System.out.println("last "+(r+1)+" values sum to prime"); return false; } r--; } // Mark i as used; add i to the path: used[i-n] = true; path[count] = i; // See if that was the last number (if so, success): if (count == size-1) return true; //System.out.println("DEBUG -- i-n=" + (i-n)); //System.out.println("possibleNbr.length=" + possibleNbr.length); //System.out.print("possibleNbr["+(i-n)+"].size() ="); //System.out.println(possibleNbr[i-n].size()); // Backtracking search over all possible next values: for (int j = 0; j < possibleNbr[i-n].size(); j++) { int k = ((Integer)possibleNbr[i-n].get(j)).intValue(); //System.out.println("DEBUG -- Looking at neighbor "+k+" of " + i); //System.out.println("k-n=" + (k-n) + ", i+k=" + (i+k)); // If we successfully extended the sequence, quit looking: if (!used[k-n] && !isPrime[i+k] && hamPath(k,count+1)) return true; } // Backtracking from here failed, so back up: used[i-n] = false; return false; } ///////////////////////////////////////////////////////////////// // Called just once to initialize array "isPrime" so that isPrime[i] // iff i is a prime. Uses a sieve. public static void initPrimes() { int sq = (int)Math.sqrt(MAX); // Largest divisor we ever need to try isPrime[0] = isPrime[1] = isPrime[4] = false; // special cases isPrime[2] = isPrime[3] = true; // special cases // Initially mark all evens as non-prime, all odds as prime: for (int i = 5; i < MAX; i +=2) { isPrime[i] = true; isPrime[i-1] = false; } // For each prime, set all multiples to "false": int start = 3; while (start <= sq) { if (isPrime[start]) { for (int j = 2*start; j < MAX; j += start) isPrime[j] = false; } start += 2; } /* DEBUG: System.out.print("Primes: "); int count = 0; for (int i = 0; i < MAX; i++) { if (isPrime[i]) { count++; if (count%16 == 0) System.out.println(); System.out.print(i+" "); } } System.out.println(); */ } }