/**
 * Die Klasse MyMath bietet saemtliche mathematische Hilfsfunktionen,
 * wie sie in den Uebungszetteln 7 bis 9 zu implementieren waren.
 * @author Manuel Haim
 */
public class MyMath {


	/**
	 * Berechnet die Quersumme einer Zahl.
	 * @param n Die Zahl, von der die Quersumme zu berechnen ist.
	 * @return Die berechnete Quersumme.
	 */
	public static int querSumme(int n) {
		int summe = 0;
		while(n!=0) {
			summe += n%10;
			n = n/10;
		}
		return summe;
	}

	/**
	 * Berechnet den groessten gemeinsamen Teiler zweier Zahlen.
	 * @param n Die erste Zahl.
	 * @param m Die zweite Zahl.
	 * @return Der groesste gemeinsame Teiler der beiden Zahlen.
	 */
	public static int ggT(int n, int m) {
		int teiler = Math.min(n, m);
		while(n%teiler!=0 || m%teiler!=0) {
			teiler--;
		}
		return teiler;
	}

	/**
	 * Berechnet den groessten gemeinsamen Teiler zweier Zahlen.
	 * Hier wird ein schnellerer Algorithmus verwendet.
	 * @param n Die erste Zahl.
	 * @param m Die zweite Zahl.
	 * @return Der groesste gemeinsame Teiler der beiden Zahlen.
	 */
	public static int ggT2(int n, int m) {
		if(n!=0 && m!=0) {
			while (n!=m) {
				if(n>m)
					n = n - m;
				else
					m = m - n;
			}
			return n;
		}
		return 1;
	}

	/**
	 * Prueft fuer eine Zahl, ob sie vollkommen ist.
	 * @param n Die zu pruefende Zahl.
	 * @return true falls die Zahl vollkommen ist, sonst false.
	 */
	public static boolean istVollkommen(int n) {
		int summe = 1;
		for(int i=2; i<=n/2; i++) {
			if(n%i==0) summe = summe + i;
		}
		if(summe==n) return true;
		return false;
	}

	/**
	 * Ausgabe aller vollkommenen Zahlen bis zu einer oberen Schranke.
	 * @param maxN Die obere Schranke.
	 */
	public static void printVollkommene(int maxN) {
		for(int i=1; i<=maxN; i++) {
			if(istVollkommen(i))
				System.out.print(" " + i);
		}
		System.out.println();
	}

	/**
	 * Prueft fuer zwei Zahlen, ob sie befreundet sind.
	 * Beispiel: 220 und 284.
	 * @param n Die erste Zahl.
	 * @param m Die zweite Zahl.
	 * @return true falls die Zahlen befreundet sind, sonst false.
	 */
	public static boolean sindBefreundet(int n, int m) {
		int summe1 = 1;
		for(int i=2; i<=n/2; i++) {
			if(n%i==0) summe1 = summe1 + i;
		}
		
		int summe2 = 1;
		for(int i=2; i<=m/2; i++) {
			if(m%i==0) summe2 = summe2 + i;
		}
		
		if(summe1==m && summe2==n) return true;
		return false;
	}
	
	/**
	 * Prueft fuer eine Zahl, ob sie eine Primzahl ist.
	 * @param n Die zu pruefende Zahl.
	 * @return true falls die Zahl eine Primzahl ist, sonst false.
	 */
	public static boolean istPrim(int n) {
		for(int i=2; i<=n/2; i++) {
			if(n%i==0) return false;
		}
		return true;
	}

	/**
	 * Gibt alle Primzahlen bis zu einer oberen Schranke aus.
	 * In der Implementierung wird das Sieb des Eratosthenes verwendet.
	 * @param maxN Die obere Schranke.
	 */
	public static void printPrimzahlen(int maxN) {
		// Initialisierung:
		boolean[] sieb = new boolean[maxN+1];
		for(int i=0; i<maxN+1; i++) {
			sieb[i] = true;
		}
		// sieb[i]==false bedeutet, dass i als nicht-Primzahl markiert ist.
		
		// Sieb des Eratosthenes:
		for(int i=2; i<=maxN; i++) {
			// Wenn i noch nicht markiert wurde...
			if(sieb[i]) {
				// ...markiere alle Vielfachen von i.
				for(int j=i+i; j<=maxN; j=j+i) {
					sieb[j] = false;
				}
			}
		}
		
		// Ausgabe:
		for(int i=2; i<=maxN; i++) {
			if(sieb[i])
				System.out.print(" " + i);
		}
		System.out.println();
	}

	/**
	 * Gibt alle Primzahlen bis zu einer oberen Schranke aus.
	 * In der Implementierung wird das Sieb des Eratosthenes verwendet,
	 * allerdings mit diversen Verbesserungen hinsichtlich der Laufzeit.
	 * Die Hauptverbesserung besteht darin, dass man nach der Markierung
	 * der Vielfachen von sqrt(maxN) abbricht (Erklaerung siehe unten).
	 * @param maxN Die obere Schranke.
	 */
	public static void printPrimzahlenVerbessert(int maxN) {
		// Initialisierung:
		boolean[] sieb = new boolean[maxN+1];
		// sieb[i]==true bedeutet, dass i als nicht-Primzahl markiert ist.
		// Standardmaessig sind boolean-Werte mit false belegt,
		// wir sparen uns also die Initialisierung, wenn wir true und
		// false vertauschen.
		
		// Sieb des Eratosthenes:
		// Die geraden Zahlen werden uebersprungen.
		// Ausserdem reicht es, wenn man nach der Markierung
		// der Vielfachen von sqrt(maxN) abbricht, da die Vielfachen
		// von groesseren Primzahlen als sqrt(maxN) bereits Vielfache
		// einer jeweils kleineren Primzahl sind.
		// Beispiel: maxN==25..35, sqrt(maxN)==5.
		//  Nachdem man alle Vielfachen von 2, 3 und 5 markiert hat,
		//  sind auch schon 2*7, 3*7, 4*7 (=2*(2*7)), 5*7 markiert,
		//  wohingegen 6*7, 7*7, 8*7, ... definitiv groesser sind als
		//  maxN (also braucht man sie nicht zu markieren).
		//  Aehnlich verhaelt es sich mit den Vielfachen von
		//  den nachfolgenden Primzahlen 11, 13, 17, ...
		int wurzel = (int) Math.sqrt(maxN);
		for(int i=3; i<=wurzel; i=i+2) {
			// Wenn i noch nicht markiert wurde...
			if(!sieb[i]) {
				// ...markiere alle Vielfachen von i.
				for(int j=i+i+i; j<=maxN; j=j+i+i) {
					sieb[j] = true;
				}
			}
		}
		
		// Ausgabe:
		System.out.print(" " + 2);
		for(int i=3; i<=maxN; i=i+2) {
			if(!sieb[i])
				System.out.print(" " + i);
		}
		System.out.println();
	}
	
}