import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to A Terribly Grimm Problem * * @author vanb */ public class grimm { public Scanner sc; public PrintStream ps; // This is a list of candidate primes for an integer in the range. // We'll base our arrays at 0, so you'll see a lot of [i-a] indices. // Note that the largest prime gap up to MaxInt is less than 300. public LinkedList candidates[] = new LinkedList[500]; public LinkedList primes = new LinkedList(); // This indicates which primes have been used. // used[p] is true if p is prime, and it has been allocated to // one of the composite numbers in the list. // Note that we only have to go up to 300 because that's // larger than the largest possible prime gap, and anything // larger than that can only be a factor in at most one // of the numbers. public boolean used[] = new boolean[500]; // gotaprime[i] is true iff the ith composite number in the list // has been allocated a prime. public boolean gotaprime[] = new boolean[500]; // This will capture the answer. public long answer[] = new long[500]; // counts[i] how many unused primes are candidates // for the ith number in the list. This will go down // as primes get allocated. public int counts[] = new int[500]; // The lower and upper bounds of the range public long a, b; // This is true if we've found a solution. boolean solved; /** * Assign a prime for a kth number * * @param k Count of how many we've done so far */ public void assign( int k ) { if( !solved ) { // Did we assign primes for all numbers a..b? if( k>b-a ) { // Print the solution for( long i=a; i<=b; i++ ) { ps.print( (i==a ? "" : " ") + answer[(int)(i-a)] ); } ps.println(); solved = true; } else { ++k; // Find the next number to allocate. // Do the lowest index, unless there's one // with only one option remaining. long n = 0; for( long i=a; i<=b; i++ ) { if( !gotaprime[(int)(i-a)] && (n==0 || counts[(int)(i-a)]==1) ) { n=i; } } gotaprime[(int)(n-a)] = true; // Go through all of the candidates for( long c : candidates[(int)(n-a)] ) if( c>b-a || !used[(int)c] ) { // Remove this from all other un-primed number's counts. // If any count goes to 0, then we fail. boolean failed = false; for( long i=a; i<=b; i++ ) { if( !gotaprime[(int)(i-a)] && candidates[(int)(i-a)].contains( c ) ) { --counts[(int)(i-a)]; if( counts[(int)(i-a)]==0 ) failed=true; } } // If we didn't fail, recurse if( !failed ) { answer[(int)(n-a)] = c; if( c<=b-a ) used[(int)c] = true; assign( k ); if( solved ) break; if( c<=b-a ) used[(int)c] = false; } // Undo the decrement of the counts for( long i=a; i<=b; i++ ) { if( !gotaprime[(int)(i-a)] && candidates[(int)(i-a)].contains( c )) { ++counts[(int)(i-a)]; } } } gotaprime[(int)(n-a)] = false; } } } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "grimm.judge" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "grimm.out" ) ); for( int i=0; i<500; i++ ) { candidates[i] = new LinkedList(); } // Build a list of all the primes up to sqrt(max), // which is just under 50000 boolean isprime[] = new boolean[100000]; Arrays.fill( isprime, true ); isprime[0] = isprime[1] = false; for( int i=0; i<100000; i++ ) if( isprime[i] ) { primes.add( i ); for( int j=i+i; j<100000; j+=i ) { isprime[j] = false; } } for(;;) { a = sc.nextLong(); b = sc.nextLong(); if( a==0 && b==0 ) break; // Go through all of the numbers in the range a..b for( long i=a; i<=b; i++ ) { // Get their prime factors, make them candidates candidates[(int)(i-a)].clear(); long n=i; for( int j : primes ) if( n%j==0 ) { candidates[(int)(i-a)].add( (long)j ); while( n%j==0 ) n/=j; if( n==1 ) break; } // Our list of primes only goes up to sqrt(max). // If there's anything left over, it must consist // of a single prime >sqrt(max) if( n>1 ) candidates[(int)(i-a)].add( n ); // This is the number of primes. counts[(int)(i-a)] = candidates[(int)(i-a)].size(); } Arrays.fill( used, false ); Arrays.fill( gotaprime, false ); solved = false; assign( 0 ); } } /** * @param args */ public static void main( String[] args ) throws Exception { new grimm().doit(); } }