import gdi.GdiMath;
import java.util.Date;

/** <B>&Uuml;bungen zu Grundlagen der Informatik</B><BR>
 * Kapitel 6 Aufgabe 1
 * @author Thomas Walter
 */
public class Eratosthenes {

	private static boolean[] erathostenes(int n) {

		boolean[] erathostenes = new boolean[n + 1];

		// Vorbelegung des Sieb-Feldes
		erathostenes[0] = false;
		erathostenes[1] = false;
		for (int i = 2; i <= n; i++)
			erathostenes[i] = true;

		// "Sieben"
		for (int i = 2; i * i <= n; i++)
			if (erathostenes[i])
				for (int k = 2 * i; k <= n; k += i)
					erathostenes[k] = false;
		return erathostenes;

	} // Erathostehnes

	public static void main(String args[]) {

		final int n = 1000000;

		boolean[] erathostenes = erathostenes(n); // Erzeugung des Siebes

		// groesste Primzahl <= n
		int probe = n;
		while (!erathostenes[probe])
			probe--;
		System.out.println(
			"\n Groesste Primzahl unter " + n + " : " + probe + "\n\n");

		// # Primzahlen bis n
		int anzahl = 0;
		for (int i = 2; i <= n; i++)
			if (erathostenes[i])
				anzahl++;
		System.out.println(
			" Anzahl der Primzahlen unter " + n + " : " + anzahl + "\n\n");

		// # Primzahlzwillinge bis n
		int anzahl2 = 0;
		for (int i = 2; i <= n - 2; i++)
			if (erathostenes[i] && erathostenes[i + 2])
				anzahl2++;
		System.out.println(
			" Anzahl der Primzahlzwillinge unter "
				+ n
				+ " : "
				+ anzahl2
				+ "\n\n");

		// 10.000. Primzahl
		int cnt = -1, nth = 0;
		while (nth < 10000 /* && cnt < erathostenes.length */
			)
			if (erathostenes[++cnt])
				nth++;
		System.out.println(" Die 10.000 Primzahl lautet : " + cnt + "\n\n");

		// Zeitvergleich
		final int[] groesse = { 10000, 1000000 };
		Date t1, t2, t3;
		int counts1, counts2;
		long dauer1, dauer2;
		for (int i = 0; i <= 1; i++) {

			// Berechnung ueber Sieb (nicht optimiert)
			t1 = new Date();
			erathostenes = erathostenes(groesse[i]);
			counts1 = 0;
			for (int j = 1; j <= groesse[i]; j++)
				if (erathostenes[j])
					counts1++;

			t2 = new Date();

			// Berechnung uer isPrime (nicht optimiert)
			counts2 = 0;
			for (int j = 1; j <= groesse[i]; j++)
				if (GdiMath.isPrime(j))
					counts2++;

			t3 = new Date();

			dauer1 = t2.getTime() - t1.getTime();
			dauer2 = t3.getTime() - t2.getTime();

			// man sieht, dass die Zeiten fuer das Sieb wesentlich
			// guenstiger sind - und dass sie wesentlich langsamer wachsen
			// als die Zeiten fuer isPrime
			System.out.println("\n # Primzahlen bis " + groesse[i] + ": \n");
			System.out.println(
				" Sieb des Eratosthenes: " + counts1 + " in " + dauer1 + " ms");
			System.out.println(
				" gdi.gdiMath.isPrime  : "
					+ counts2
					+ " in "
					+ dauer2
					+ " ms\n\n");

		} // for

	} // main

} // Eratosthenes