import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.PrintStream; import java.util.Random; import java.util.Scanner; /** * Composite Numbers * * For the UMD High School Programming Contest, 2009. * @author Chau-Wen Tseng */ public class Composites { public static void main(String[] args) throws Exception { int testStart = 0; int testStop = 0; long time; Scanner sc = new Scanner(System.in); // System.err.println("Processing input: " + line); // skip past empty lines while (sc.hasNextInt()) { testStart = sc.nextInt(); testStop = sc.nextInt(); // System.out.println(Integer.MAX_VALUE); time = System.currentTimeMillis(); sieveAlg1(testStart, testStop); time = System.currentTimeMillis() - time; // System.err.println("Sieve Time = "+(time/1000)); /* time = System.currentTimeMillis(); simpleAlg(testStart, testStop); time = System.currentTimeMillis() - time; System.err.println("Simple Time = "+(time/1000)); */ } } public static void simpleAlg (int testStart, int testStop) { int seqLen = 1; int seqStart = 0; int seqEnd = 0; int start = testStart; for (int i = testStart; i<= testStop; i++) { if (isPrime(i)) { // sequence is from start to i-1 int len = (i)-start; if ((start != 0) && (len >= seqLen)) { seqStart = start; seqEnd = i-1; // System.out.println(seqStart + " to " + seqEnd + ": " + len); seqLen = len; } start = 0; } else { if(start == 0) start = i; if (i == testStop) { int len = (i)-start+1; if ((start != 0) && (len >= seqLen)) { seqStart = start; seqEnd = i; // System.out.println(seqStart + " to " + seqEnd + ": " + len); seqLen = len; } } } } System.err.println(seqStart + " to " + seqEnd + " length = " + seqLen); } public static void sieveAlg1 (int testStart, int testStop) { int limit = 1 + (int) Math.sqrt((double) testStop); boolean [] flags = new boolean[testStop+1]; // initialize flags for (int i=0; i <= testStop; i++) { flags[i] = true; } // for all divisors from 2 to sqrt(top of range) for (int d = 2; d < limit; d++) { // if divisor is prime if (flags[d]) { // remove all multiples of prime d for (int k=d+d; k <= testStop; k+=d) { flags[k] = false; } } } // check for longest run of composite numbers int seqLen = 1; int seqStart = 0; int seqEnd = 0; int start = testStart; for (int i = testStart; i<= testStop; i++) { if (flags[i]) { // sequence is from start to i-1 int len = i-start; if ((start != 0) && (len >= seqLen)) { seqStart = start; seqEnd = i-1; // System.out.println(seqStart + " to " + seqEnd + ": " + len); seqLen = len; } start = 0; } else { if (start == 0) start = i; if (i == testStop) { int len = i-start+1; if ((start != 0) && (len >= seqLen)) { seqStart = start; seqEnd = i; // System.out.println(seqStart + " to " + seqEnd + ": " + len); seqLen = len; } } } } System.out.println(seqStart + " " + seqEnd); } public static boolean isPrime(int num) { int limit = (int) Math.sqrt((double) num); for ( int i = 2; i <= limit; i++ ) { if ( num % i == 0 ) return false; } return true; } }