1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 914 - Jumping Champion
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=855
* @author Mitterreiter Christian
* @author Posselt Christian
* @version 1.0, 05/18/2011
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.796
*/


import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

public class Main {

/**
* Für jeden Primzahlsprung die Anzahl des Auftretens in eine Map speichern
* @param m Map
* @param zahl Primzahlsprung
*/
public static void add(Map<Integer, Integer> m, int zahl) {
if (m.containsKey(zahl)) {
m.put(zahl, (m.get(zahl)) + 1);
} else {
m.put(zahl, 1);
}

}

public static void main(String[] args) {
//7
int n = 1000004;
int quadrat = 0;

boolean[] maske = new boolean[n];

for (int i = 0; i < n; i++)
maske[i] = true;
maske[0] = false;
maske[1] = false;

// Sieb des Eratosthenes
for (int i = 1; i < n; i++) {
quadrat = quadrat + 2 * i - 1;
if (quadrat > n)
break;
if (maske[i])

for (int j = 2 * i; j < n; j += i)
maske[j] = false;
}

//Ergebnismaske in Zahlen umrechnen
long[] primes = new long[n / 5];
int index = 0;
for (int j = 0; j < maske.length; j++) {
if (maske[j] == (true)) {
primes[index] = j;
index++;
}
}

//Primzahlsprünge
long[] jump = new long[primes.length];

//berechnet für 2 aufeinander folgende Primzahlen die Differnenz
for (int i = 0; i < jump.length - 1; i++) {
jump[i] = primes[i + 1] - primes[i];
}


////////////////////////////////////////////////////////////////////////////////////

Scanner s = new Scanner(System.in);
//Anzahl der Testfälle einlesen
int tests = s.nextInt();

while (tests > 0) {

//obere und untere Schranke einlesen
int min = s.nextInt();
int max = s.nextInt();
int indexMin = 0;
int indexMax = 0;

//Map in der der Jeweilige Primzahlsprung mit der Anzahl des Auftretens gespeichert wird
Map<Integer, Integer> count = new HashMap<Integer, Integer>();

//Sucht die erste Primzahl im Intervall
for (int i = 0; i < primes.length; i++) {
if (primes[i] >= min) {
indexMin = i;
break;
}
}

//Sucht die letzte Primzahl im Intervall
for (int i = indexMin; i < primes.length; i++) {
if (primes[i] > max) {
indexMax = i - 1;
break;
}
}

//ermittelt für jeden Primzahlsprung im Intervall die jeweilige Häufigkeit
for (int i = indexMin; i < indexMax; i++) {
add(count, (int) jump[i]);
}

int champ = -1;
int champ_count = -1;
boolean doppelt = false;

Iterator<Integer> i = count.keySet().iterator();
//sucht die am häufigst vorkommende Prim
while (i.hasNext()) {
int currentJump = i.next();
int anzahl = count.get(currentJump);

if (anzahl == champ_count)
doppelt = true;
if (anzahl > champ_count) {
doppelt = false;
champ_count = anzahl;
champ = currentJump;
}

}

//Ergebnisausgabe
if (doppelt || champ == -1)
System.out.println("No jumping champion");
else
System.out.println("The jumping champion is " + champ);

tests--;
}
}
}

2.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/**
* FWP, Ausgewhlte Probleme aus dem ACM Programming Contest, SS11
* Problem: 914 Jumping Champion
* Link:
http://w3-o.cs.hm.edu/~logofatu/FWPACM/SS11/contestSimulation18_05.pdf
*
* @author Rolf Schirm
* @version 1.0, 05/18/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.656
*/
public class Main {

private static final int MAX_NUMBER = 1000000/8;
private static int currentNumber = 2;
private static final int[] PRIMES = new int[MAX_NUMBER+1];
public static void main(String... args) throws Exception {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

// Init first prime
PRIMES[0] = 1 << 2;

final int tcCount = Integer.parseInt(reader.readLine());
for(int xyz = 0; xyz < tcCount; xyz++) {
final String[] split = reader.readLine().split(" ");
final int startNumber = Integer.parseInt(split[0]);
final int endNumber = Integer.parseInt(split[1]);

// Init primes if necessary
if(currentNumber < endNumber) {
initPrimesUntil(endNumber);
}

// Map for counting the numbers
Map<Integer, Integer> numberCount = new HashMap<Integer, Integer>();

int lastPrime = -1;
int bestJumpRange = 0;
int bestJumpCount = 0;
boolean isJumpValid = false;
for(int i = startNumber; i <= endNumber; i++) {
// Check if its a prime
if(isPrime(i)) {
if(lastPrime != -1) {
int jump = i - lastPrime;
if(!numberCount.containsKey(jump)) {
numberCount.put(jump, 0);
}
int count = numberCount.get(jump) + 1;
numberCount.put(jump, count);

// Multiple jumping champions
if(count == bestJumpCount) {
isJumpValid = false;

// New jumping champion
} else if(count > bestJumpCount) {
bestJumpRange = jump;
bestJumpCount = count;
isJumpValid = true;
}
}
lastPrime = i;
}
}

// Print result
if(isJumpValid) {
System.out.println("The jumping champion is " + bestJumpRange);
} else {
System.out.println("No jumping champion");
}
}
}

private static void initPrimesUntil(int endNumber) {
for(int i = currentNumber + 1; i <= endNumber; i++) {
int root = (int) Math.sqrt(i);
boolean isPrime = true;
for(int j = 2; j <= root && isPrime; j++) {
isPrime = i % j != 0;
}
if(isPrime) {
setPrime(i);
}
}
currentNumber = endNumber;
}

private static boolean isPrime(int i) {
final int arrayIndex = i / 8;
final int bitIndex = i % 8;

return (PRIMES[arrayIndex] & (1 << bitIndex)) != 0;
}

private static void setPrime(int i) {
final int arrayIndex = i / 8;
final int bitIndex = i % 8;

PRIMES[arrayIndex] |= 1 << bitIndex;
}
}




------------------------------


1.

/*
* ACM Contest training
* Problem: 914 - Jumping Champion
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=855
*
* @author Patrick Bedat, Philippe Brousse, Christoph Goettschkes
* @version 1.0, 11/14/2010
*
* Method : Sieve of Eratosthenes
* Status : Accepted
* Runtime: 0.232
*/

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.*;

class Main
{
static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

static BitSet primeSet = new BitSet(1000001);
static List<Integer> primeList = new ArrayList<Integer>();

public static void main(String[] agrs) throws IOException
{
sieve();
int testCases = Integer.parseInt(reader.readLine());

for (int curCase = 0; curCase < testCases; curCase++) {
String[] line = reader.readLine().split(" ");
int from = Integer.parseInt(line[0]);
int to = Integer.parseInt(line[1]);

if (from > to) {
int temp = to;
to = from;
from = temp;
}

int fromPrime = from;
for (int i = from; i <= to; i++)
if (!primeSet.get(i)) {
fromPrime = i;
break;
}

int toPrime = to;
for (int i = to; i >= from; i--)
if (!primeSet.get(i)) {
toPrime = i;
break;
}

if (primeSet.get(toPrime) || fromPrime == toPrime) {
System.out.println("No jumping champion");
continue;
}

int start = Collections.binarySearch(primeList, fromPrime);
int end = Collections.binarySearch(primeList, toPrime);
int[] divs = new int[primeList.get(end) - primeList.get(start) + 1];

boolean champ = false;
int maxDivs = 0;
int index = 0;

for (int i = start; i < end; i++) {
int div = primeList.get(i + 1) - primeList.get(i);
divs[div]++;
if (maxDivs < divs[div])
{
maxDivs = divs[div];
index = div;
champ = true;
} else if (maxDivs == divs[div])
champ = false;
}

if (champ)
System.out.println("The jumping champion is " + index);
else
System.out.println("No jumping champion");

}
}

static void sieve() {
int max = 1000000;
int root = (int) Math.sqrt(1000001);
primeSet.set(1, true);
primeSet.set(0, true);
for (int m = 2; m <= root; m++)
if (!primeSet.get(m))
for (int k = m*m; k <= max; k += m)
primeSet.set(k, true);

for (int m = 2; m <= max; m++)
if (!primeSet.get(m))
primeList.add(m);
}
}