import algds.IOUtils;
import mathe.FormattedOut;
/**
 * AlgDs WS99 Aufgabe 07.
 * Prueft ob eine eingegebene Zahl eine Primzahl ist oder nicht.<br>
 *
 * Enth&auml;lt zwei Versionen des Primzahltests:<br>
 * die einfache Version, die durch alle ungeraden Zahlen bis zur Wurzel teilt,<br>
 * und eine verbesserte Version, die f&uuml;r gro&szlig;e Zahlen
 * deutlich weniger Teilungen braucht (daf&uuml;r auch deutlich gr&ouml;&szlig;er ist).
 *
 * @author Christian Semrau, 1.11.1999, 05.12.1999, 24.12.1999<br>
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
public class ChS_Aufg07 {
static int divs;

public static void main(String[] args) {
  long zahl;

  System.out.println(
	"Welche Zahl soll auf ihre Primzahleigenschaft geprueft werden?");
  do {
	System.out.print("[0=Ende]:");
	zahl = IOUtils.readLong();
	if (zahl>0) printlnIsPrim(zahl);
  } while (zahl>0);
} // main()           

/**
 * Einfache Version.<br>
 * Liefert den kleinsten Teiler von abs(zahl).
 * 0 wenn zahl==0; 1 wenn abs(zahl) ist Primzahl; sonst kleinsten Teiler von abs(zahl)
 * @return int der kleinste Teiler von zahl
 * @param zahl die zahl, deren kleinster Teiler bestimmt werden soll
 */
public static long minteiler(long zahl) {
  divs = 0;
  if (zahl<0) zahl=-zahl;    // wir verarbeiten auch negative Zahlen
  if (zahl==0) return(0);    // 0 hat als einzige Zahl minteiler 0
  if (zahl<=2) return(1);    // 1 hat Teiler 1 und 2 ist prim
  divs++;
  if (zahl%2==0) return(2);  // gerade Zahlen durch 2 teilbar
  long wurzel = (long)Math.sqrt(zahl);    // abgerundete Wurzel der Zahl

  for(long i = 3; i <= wurzel; i += 2) { // alle ungeraden bis zur Wurzel
	divs++;
	if (zahl%i==0)  // Teilbarkeit testen
	  return(i);    // Teiler zurueckgeben
  }

  // keine Teiler gefunden
  return(1);  // zahl ist prim
}

/**
 * Verbesserte Version.<br>
 * Liefert den kleinsten Teiler von abs(zahl).
 * 0 wenn zahl==0; 1 wenn abs(zahl) Primzahl; sonst kleinsten Teiler(>1) von abs(zahl)
 * @return int der kleinste Teiler von zahl
 * @param zahl die zahl, deren kleinster Teiler bestimmt werden soll
 */
public static long minteiler2357(long zahl) {
  divs=0;
  if (zahl<0) zahl=-zahl;    // wir verarbeiten auch negative Zahlen
  if (zahl==0) return(0);    // 0 hat als einzige Zahl minteiler 0

  // mit welchen Primzahlen wir die Zahl vergleichen, bevor es eigentlich losgeht...
  int[] lprim = {1,2,3,5,7,11};

  // testet ob zahl =1 oder eine der Primzahlen 2..11 ist
  for (int i=0; i<lprim.length; i++)
	if (zahl==lprim[i]) return(1);

  for (int i=1; i<lprim.length; i++) {
	// testet ob zahl ein Vielfaches der Primzahlen 2..11 ist
	divs++;
	if (zahl%lprim[i]==0) return(lprim[i]);
	// wenn zahl kleiner ist als das Quadrat der folgenden Primzahl,
	// dann ist zahl eine Primzahl
	// testet nicht fuer die die letzte Primzahl der Liste,
	// da dann die naechste fehlt
	if (i+1<lprim.length && zahl<lprim[i+1]*lprim[i+1]) return(1);
  }

/*
 Anzahl der Testdivisionen der Hauptschleife:
 fuer grosse Zahlen: ~ 43:210 = 1/5+1/210 ~ 0.2048
 testet ca 20% aller Zahlen bis zur Wurzel von zahl
 testet fuer zahl <= sqr(223)-1 = 49728 keine Zahl zuviel
 im Gegensatz zum einfachen (i=3; i<=sqrt(zahl); i+=2)
 welcher 50% aller Zahlen bis zur Wurzel testet
*/
  int l = 2*3*5*7; // =210
  // 1 und alle Primzahlen >7 und <210
  int[]prim = {1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,
	  103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199};

  int[]REST = new int[l];  // welcher der naechste Rest ist
  int[] ADD = new int[l];  // was bis zur naechsten Zahl fehlt
  for (int i=0; i<prim.length; i++) {
	REST[prim[i]] = (i==prim.length-1)?1:prim[i+1];
	ADD [prim[i]] = ((i==prim.length-1)?l+1:prim[i+1]) -prim[i];
  }

  long wurzel = (int)Math.sqrt(zahl);   // abgerundete Wurzel der Zahl
  long i; int rest;
  for(i = rest = prim[1]; i <= wurzel; i += ADD[rest], rest = REST[rest]) {
  // bis zur Wurzel durch alle teilen, die mit 210 einen Primrest lassen
	divs++;
	if (zahl%i==0)  // Teilbarkeit testen
	  return(i);    // Teiler zurueckgeben
  }

  // keine Teiler gefunden
  return(1);  // zahl ist prim
}

/**
 * F&uuml;hrt beide Versionen aus und vergleicht die Anzahl der
 * n&ouml;tigen Divisionen.
 *
 * @param zahl Welche Zahl getestet werden soll
 */
public static void printlnIsPrim(long zahl) {
  long teiler=minteiler(zahl);
  System.out.println("Einfache Version:"+divs+" divs");
  long teiler2=minteiler2357(zahl);
  System.out.println("Verbesserte Version:"+divs+" divs");
  if (teiler!=teiler2)
	System.out.println("Fehler fuer "+zahl+": t1="+teiler+", t2="+teiler2);
  if (teiler<=1)
	System.out.println(zahl+" ist Primzahl.");
  else
	System.out.println(zahl+" ist teilbar durch "+teiler+".");
}
} // class ChS_Aufg07