//***********************************************************************
//*Beschreibung		: Euler'sche Funktion			 					*
//*Autor			: Thomas Tardy										*
//*Datum			: 02.01.03											*
//*Fach				: Mathematik										*
//***********************************************************************

public class Euler
{
	static public void main( String[] args )
  	{
		long zahl, resultat;
		long euler=0;
		long eulerrest=0;
		long nZahl=1;
		System.out.println("***EULER'SCHE FUNKTION***\n");
		System.out.print("Geben Sie bitte eine natuerliche Zahl ein: ");
		zahl=(long) InOut.getDouble();
		while(nZahl<zahl)
		{
			euler=feuler(zahl,nZahl);
			eulerrest=eulerrest+euler;
			System.out.println(nZahl);
			nZahl++;
		}
		resultat=zahl-eulerrest;
		System.out.println("\n\n");
		System.out.print("Das Resultat lautet: ");
		System.out.println(resultat);
	}

	static public long feuler ( long zahl, long nZahl)
	{
		long teiler, euler;
		teiler=ggT(zahl, nZahl);
		if(teiler<=2)
		{
			if(teiler==0)
			{
				euler=0;
			}
			else
			{
				euler=1;
			}
		}
		else
		{
			euler=0;
			long eulerrest=0;
			zahl=teiler;
			nZahl=1;
			while (nZahl<zahl)
			{
				euler=feuler(zahl,nZahl);
				eulerrest=eulerrest+euler;
				nZahl++;
			}
			euler=zahl-eulerrest;
		}
		return euler;
	}

	static public long ggT ( long zahl, long nZahl)
	{
		long teiler, c;
		long a=zahl;
		long b=nZahl;
		while(b>0)
		{
			if (a>=b)
			{
				a=a-b;
			}
			else
			{
				c=b;
				b=a;
				a=c;
			}
		}
		if (a==nZahl)
		{
			teiler=a;
		}
		else
		{
			teiler=0;
		}
		return teiler;
	}
}