// Javascript zum Berechnen von Termen
// (c) Arndt Brünner, 25. 10. 2001
// Version: 21. 4. 2003


var programmiert=0;
var xStr="", fStr="", FStr="";
var whelp;
var trigo=0,Grad_rad=Math.PI/180,Rad_grad=180/Math.PI,grad_rad,rad_grad;
var m0=0,m1=0,m2=0,m3=0,m4=0,m5=0,m6=0,m7=0,m8=0,m9=0;

function rechner()
{
grad_rad=(trigo==1)?Grad_rad:1;rad_grad=(trigo==1)?Rad_grad:1;
document.f.e.value="";
p=document.f.t.value;
if(p=="rad"){trigo=0; document.f.e.value="Bogenmaß aktiviert";if(programmiert==1)parse(FStr);return;}
if(p=="grad"){trigo=1; document.f.e.value="Gradsystem aktiviert";if(programmiert==1)parse(FStr);return;}
if(p=="f?"){if(programmiert==1){document.f.t.value=FStr;return;}else {document.f.e.value="derzeit nicht programmiert";return;}}
ee=parse(document.f.t.value);
if((programmiert==1)&&(ee.indexOf("rammiert")==-1))ee="f("+p+")="+ee;
document.f.e.value=ee;
document.f.t.focus();
if(document.f.e.value.indexOf("rogramm")>0)document.f.t.select();
}

function parse(p)
{ 
if((p.indexOf("newton")==-1)&&(p.indexOf("solve")==-1)&&(p.indexOf("=")>-1)&&(p.indexOf("x")>-1))p="solve("+p+")";
if(p.indexOf("(")>-1)if(p.match(/\(/g).length!=p.match(/\)/g).length)return"Klammerfehler";
a=String(p).replace(/,/g,".").replace(/F/,"f");
if(a.length==0){return "?";}
if(a.substr(0,4)=="f(x)"){xStr=a.substr(2,1);fStr=translate(a.substr(5,a.length-3));FStr=p;if(fStr!=""){programmiert=1;return "Programmiert";}}
if((fStr=="")&&(programmiert==1)) {programmiert=0;return "Programmierung gelöscht";}
F=a.replace(/\./g,",");
var f=translate(a);//alert(f);
if(((f=="(X)")||(f=="X"))&&(programmiert==1)){programmiert=0;fStr=""; return "Programmierung gelöscht";}
if((f.indexOf("X")>-1)&&(f!="(X)")&&(p.indexOf("newton")==-1)&&(f.indexOf("solve")==-1)){xStr="X";fStr=f;programmiert=1;FStr=p;return "Programmiert";}
if(programmiert==1){f=fStr.replace(/X/g,"("+translate(a)+")");}
if(f.indexOf("solve")>-1)
{
	return eval(f);
}
var EE;
ee=Runden(EE=eval(f),13);//alert(ee);
if(isNaN(ee))ee=EE;
eee=new String();
eeee=eee=String(ee);
if(document.f.alsbruch!=null)
if(document.f.alsbruch.checked)
{
	eee=String(GetBruch2(ee));
	if(eee=="")eee=String(GetBruchKB(ee,1e-14,1000));
	if(eee=="")eee=String(GetBruch(ee,1e-8,10));
	if(eee==eeee.replace(/\./,","))eee=String(GetBruchKB(ee,1e-12,1000000));
	if(eee=="")eee=String(ee);
}
eee=eee.replace(/\./,",").replace(/-,/,"-0,")
if(eee.substr(0,1)==",") eee="0"+eee;
return eee;
}

function showHelp()
{
if((!whelp)||(whelp.closed)) whelp=window.open("rechnerhilfe.htm","rechnerhilfe");
whelp.focus();
}

function repair()
{
t=String(document.f.terme.value);
t=t.replace(/ /g,"");
t=t.replace(/\r\n/g,"|");
a=t.split("|");
for(i=0;i<a.length;i++)
for(j=i+1;j<a.length;j++)
if(a[i]==a[j])a[j]="";
t=a.join("|");
while(t.indexOf("||")>-1)t=t.replace(/\|\|/g,"|");
t=t.replace(/\|/g,"\n");
document.f.terme.value=t;
}

function translate(t)
{
	var MultErg=new Array(/\d[a-z]/,/\d\(/,/\)\(/,/x\(/,/\)x/,/pi\(/,/e_\(/,/\dpi/,/\de_/,/\)[a-z]/);
	for(j=0;j<MultErg.length;j++)
		do{i=t.search(MultErg[j]);if(i==-1)break;t=t.substr(0,i+1)+"*"+t.substring(i+1,t.length);}while(true);
t="("+t+")";
var n=0,d;
var j=0,k=0,i=0;
t=t.replace(/'/g,"^");
if(t.indexOf("^")>-1)
for(i=0;i<t.length;i++)
if (t.substr(i,1)=="^")
{j=parsefind(t,i,-1); k=parsefind(t,i,1);
t=t.substring(0,j+1)
+ "Math.pow(" 
+ t.substring(j+1,i)
+ ","+t.substring(i+1,k)+")"
+ t.substring(k,t.length);
n++;if(n>15)break;
}n=0;
if(t.indexOf("!")>-1)
for(i=0;i<t.length;i++)
if (t.substr(i,1)=="!")
{j=parsefind(t,i,-1);
t=t.substring(0,j+1) + "fak(" + t.substring(j+1,i)+")"+ t.substring(i+1,t.length);
n++;if(n>15)break;}
	if(t=="") return "(0)";
	if(t==null) return;
	var tt=t;
	t=t.replace(/solve/g,"solvä");
	t=t.replace(/eile/g,"äilä");
	t=t.replace(/legendre/g,"lägändrä");
	t=t.replace(/factor_vec/g,"factor_väc");
	t=t.replace(/newton/g,"näwton");
	t=t.replace(/fresnelc/gi,"fräsnälc");
	t=t.replace(/fresnels/gi,"fräsnäls");
	t=t.replace(/\n/g,"").replace(/\r/g,"");
//	t=t.replace(/\+/g,"+");
	t=t.replace(/\-/g,"-");
	t=t.replace(/\—/g,"-");
	t=t.replace(/\–/g,"-");
	t=t.replace(/\·/g,"*");
	t=t.replace(/\*/g,"*");
	t=t.replace(/\//g,"/");
	t=t.replace(/modpow/gi,"m@dp@w");
	t=t.replace(/modmult/gi,"m@dmult");
	t=t.replace(/mod/gi,"%");
	t=t.replace(/ \^ /g,"^");
	t=t.replace(/Math\./g,"").replace(/sqrt/g,"sqr");
	t=t.replace(/pow/gi,"Math.pow");
	t=t.replace(/m\@dp\@w/g,"modpow");
	t=t.replace(/m\@dmult/g,"modmult");
	//if (trigo==0)
	{
	t=t.replace(/atanh/gi,"at~anh");
	t=t.replace(/asinh/gi,"as~inh");
	t=t.replace(/acosh/gi,"ac~osh");
	t=t.replace(/sinh/gi,"sinh");
	t=t.replace(/cosh/gi,"cosh");
	t=t.replace(/tanh/gi,"tanh");
	t=t.replace(/coth/gi,"coth");
	t=t.replace(/acoth/gi,"cot");
	t=t.replace(/atan/gi,"at~an");
	t=t.replace(/asin/gi,"as~in");
	t=t.replace(/acos/gi,"ac~os");
	t=t.replace(/acot/gi,"cot");
	t=t.replace(/sin/gi,"sin");
	t=t.replace(/cos/gi,"cos");
	t=t.replace(/tan/gi,"tan");
	t=t.replace(/cot/gi,"cot");
	t=t.replace(/ascsh/gi,"ascsh");
	t=t.replace(/ascs/gi,"ascs");
	t=t.replace(/scsh/gi,"scsh");
	t=t.replace(/scs/gi,"scs");
	t=t.replace(/°/g,"*(pi)/180");
      }if(trigo==1)t=t.replace(/°/g,"");
	t=t.replace(/sqrt/gi,"sqr");
	t=t.replace(/sqr/gi,"Math.sqrt");
	t=t.replace(/abs/gi,"Math.abs");
	t=t.replace(/int/gi,"Math.floor");
	t=t.replace(/log\(/gi,"Math.log(");
	t=t.replace(/ln/gi,"Math.log");
	t=t.replace(/geoM/gi,"gäoM");
	t=t.replace(/asech/gi,"asäch");
	t=t.replace(/sech/gi,"säch");
	t=t.replace(/asec/gi,"asäc");
	t=t.replace(/sec/gi,"säc");
	t=t.replace(/exp/gi,"Math.ä@p");
	t=t.replace(/cent/gi,"cänt");
	t=t.replace(/sv\(/gi,"sv(");
	t=t.replace(/kgv/gi,"kgV");
	t=t.replace(/ggt/gi,"ggT");
	t=t.replace(/x/g,"X").replace(/y/g,"Y");
	t=t.replace(/pi/gi,"Math.PI");
	t=t.replace(/\de/gi,"ä");
	t=t.replace(/e/gi,"(Math.E)");
	t=t.replace(/ä/g,"e").replace(/@/g,"x");
	t=t.replace(/\~/g,"");
	t=t.replace(/\|/g,","); //alert(t);
	if(t.indexOf("solve(")>-1)
	{
		i=0;var ii=0,iii,ts=t;
		do{
			iii=ts.indexOf("solve(");
			if(iii==-1)break;
			ii=parsefind(ts,iii,1);
			t=t.substr(0,iii+i+6)+"'"+t.substring(iii+i+6,ii+i-1)+"'"+t.substring(ii+i-1,t.length);
			i+=iii+1;
			ts=ts.substring(ii+1,ts.length);
		}while(true);
	}
	while(t.search(/p\d/)>-1)
			{i=t.search(/p\d/);j0=parsefind(t,i,-1);
			j1=parsefind(t,i,1);d=DezToBruch(t.substring(j0+1,j1));
			t=t.substr(0,j0+1)+"("+d+")"+t.substring(j1,t.length);}
if (t=="") t="0";
//alert(t);
return t.substr(1,t.length-2);
}

function parsefind(t,i,r)
{
var L_=t.length, k=0, j=0;
for(j=i+r;(j<L_)&&(j>=0);j+=r)
{
var u=t.substr(j,1);
if(u=="(")k++; else if(u==")")k--;
if(k*r<0)return j;
if((k==0)&&((u=="+")||(u=="-")||(u=="*")||(u=="/")||(u==";")||(u==",")||(u=="=")||(u=="\"")||(u=="'")||(u=="|")||(j+r==L_+1)||(j+r==-1))) return j;
}
return j;
}

function GetBruch(x,d,max)
{
	if(String(x).indexOf("e")>-1)return x;
	var y;
	var vz=(x<0)?-1:1;
	x=Math.abs(x); 
	for(var i=1;i<=max;i++)
	{
		y=x*i;
		if(Math.abs(y-Math.floor(y+0.5))<=d) {Nenner=i;Zaehler=y; if (i>1.5){return vz*Math.floor(y+0.5)+"/"+i;} else return vz*Math.floor(y+0.5);}
	}
      var xx=x*x;
	if(((x!=Math.floor(x))&&(Math.floor(xx)==xx))||(Math.abs(xx)<d)) return String(x*vz).replace(/\./g,",");
	for(i=1;i<=1000;i++)
	{
		y=i*xx;if((Math.abs(y)>1e+8)||(Math.abs(y)<d)){break;}
		if(Math.abs(y-Math.floor(y+0.5))<=d) 
		{
			y=Math.floor(y+.5); 
			nenner=Math.sqrt(i);Nenner=(nenner==Math.floor(nenner))? nenner : "sqr("+i+")";
			zaehler=Math.sqrt(y);Zaehler=(zaehler==Math.floor(zaehler))? zaehler : "sqr("+y+")";
//			Nenner=i;Zaehler=y; if (i>1.5){return vz*Math.floor(y+0.5)+"/sqr("+i+")";} else{ return vz*Math.floor(y+0.5);}}
			if (i==1){return ((vz==-1)?"-":"")+Zaehler; }else return ((vz==-1)?"-":"")+Zaehler+"/"+Nenner;
		}
	}

	return String(x*vz).replace(/\./g,",");
}

function GetBruch2(x)
{
if(String(x).indexOf("e")>-1)return x;
var vorz="";
if(x<0){x=-x;vorz="-";}
i=(t=String(x)).indexOf(".");if(i==-1) return vorz+x;
if((t.length-i>10)||(t.length>15)) return "";
z=Number(t.substring(0,i)+t.substring(i+1,t.length));
n=Number(1+"00000000000000000000000000000000000000".substr(0,t.length-i-1));
ggt=ggT(z,n);
return vorz+(z/ggt)+"/"+(n/ggt);
}

function GetBruchKB(x,d,nn)
{
if(Math.round(x)==x){return "";}
var q=Math.abs(x),r=1;
var vz=(x<0)?"-":"";
while(Math.round(q)!=q){q*=10;r*=10;}
//var B=new Array(q,r);
//r=Number(B[1]),q=Number(B[0]);
//r=164;q=371;
var rr=q%r,c=r;
q=Math.floor(q/r);r=rr;
var a2=0,a1=1,a0=q,b2=1,b1=0,b0=1;
while(b0<=nn){
	q=Math.floor(c/r);rr=c%r;c=r;r=rr;
	var aa=q*a0+a1;a2=a1;a1=a0;a0=aa;
	var bb=q*b0+b1;b2=b1;b1=b0;b0=bb;
	if(Math.abs(a1/b1-Math.abs(x))<d)break;
	//alert("a0="+a0+"\nb0="+b0+"\nb="+q+"\na1="+a1+"\nb1="+b1+"\na2="+a2+"\nb2="+b2);
	//if(b1>nn)break;
}//alert(Math.abs(a1/b1-Math.abs(x))+"\n"+d);
if(Math.abs(a1/b1-Math.abs(x))>d)return "";
nm=b1;zm=a1;
return vz+zm+((nm==1)?"":"/"+nm);
}

function DezToBruch(d)
{
var g="";
ub=false;
d=d.replace(/,/g,".").replace(/ +/g,"");
if(Number(d)<0){g="-";d=d.substring(2,d.length);}
ik=d.indexOf(".");
if(ub){g+=d.substr(0,ik)+" ";d="0."+d.substring(ik+1,d.length);ik=1;}
if(d=="")return "";
ip=d.indexOf("p");if(ip<0)ip=d.length;
bruch=GetBruch2(d.substr(0,ip));
if(ip==d.length) return g+bruch;
if(ik==-1)return "";
p=d.substr(ip+1,d.length-ip);
if (p.length==0)return "";
ib=bruch.indexOf("/");
z1=Number(bruch.substr(0,ib));n1=Number(bruch.substr(ib+1,bruch.length-ib));
n2=Number("999999999999999999999".substr(0,p.length)+"00000000000000000".substring(ik+1,ip));
nn=n1*n2/ggT(n1,n2)
zz=z1*nn/n1+p*nn/n2;
ggt=ggT(nn,zz);
nn/=ggt;zz/=ggt;
if((ub)&&(g!=0))return g+zz+"/"+nn; else return zz+"/"+nn;
}


function ggT(a,b)
{
    if((isNaN(a))||(isNaN(b)))return 1;
    if(((a%1)!=0)||((b%1)!=0))return 1;
    a=Number(a);b=Number(b);
    if (a*b == 0) return 1;
    do
    {
        c = a%b;
        a = b;
        b = c;
    }while (c != 0);
    return a;
}
function kgV(a,b){return a*b/ggT(a,b);}

function fak(x)
{
x=Math.floor(x);
if(x<=1)return 1;
return x*fak(x-1);
}

function bk(n,k)
{if(k>n){alert("Die Berechnung des Binomialkoeffizienten bk(n|k) bedingt, daß n>=k sein muß.");return;}
if((Math.floor(n)!=n)||((Math.floor(k)!=k))||(k>n)||(k<0)||(n<0))return "Error";
var b=1; for(i=1;i<=k;i++)b/=(n-i+1)/i;return Math.round(1/b);
}

function pow(x,y)
{
if(y!=Math.floor(y))return Math.pow(x,y);
if(y==0)return 1;
var p=1/x; if(y<0){for(i=1;i<-y;i++)p/=x;return p;}
p=x;for(i=1;i<y;i++){p*=x;}
if(Math.floor(x)==x)return Math.round(p);
return p;
}

function rnd(x)
{
if(isNaN(x))return Math.random();
return Math.random()*x;
}

function rndN(a,b)
{
	return Math.floor(Math.random()*(b-a+1)+a);
}

function Runden(t,i)
{
	if(t==Math.floor(t))return t;
	var d=Math.round(Math.pow(10,i));
	return Math.round(t*d)/d;
}
var newtonretx=(1==0);

function solve(t)
{
	var x,v,y,yy=null,q="1",l=new Array(),n=0,i,ii;
	t=t.replace(/"/g,"");
	i=t.indexOf("=");
	if(i>-1)t=t.substr(0,i)+"-("+t.substring(i+1,t.length)+")";
	for(i=0;i<20;i++)
	{
		x=Math.random()*10-5;
		y=eval(t.replace(/X/g,"x"));
		if((y!=null)&&(Math.abs(y)<1000000))
		{
			if(yy==null)yy=y;
			else
			if(Math.abs(y-yy)>0.00001)break;
		}
	}
	if(i==20)return (Math.abs(y)<1e-12)?"L = R":"L = {}";
	for(x=0;x<20;x++)
	{
		if(Math.abs(eval(t.replace(/X/g,"("+x+")")))<1.0e-12)
		{
			for(ii=0;ii<l.length;ii++)if(x==l[ii])break;
			if(ii==l.length)l[l.length]=x;
		}
		if(Math.abs(eval(t.replace(/X/g,"("+(-x)+")")))<1.0e-12)
		{
			for(ii=0;ii<l.length;ii++)if(x==l[ii])break;
			if(ii==l.length)l[l.length]=-x;
		}
	}
	newtonrext=false;
	for(i=0;i<=100;i++)
	{
		x=Math.random()*Math.random()*Math.random()*1000;
		if(Math.random()>.8)x=Math.random()*2;
		if(Math.random()>.5)x*=-1;
		y=newton_((n+1)+"*("+t+")/("+q+")",x,20,1.0e-12);
		if(y!=null)
		{ 
			y=Runden(y,10);
			if((y==Infinity)||(y==-Infinity))continue;
			for(ii=0;ii<l.length;ii++)if(Math.abs(l[ii]-y)<0.001)break;
			if(ii<l.length)continue;
			q+="*(x"+((y<0)?"+":"-")+Math.abs(y)+")";
			l[l.length]=y;n*=y;
		}
	}
	quicksort(l);
	if(document.f.alsbruch!=null){if(document.f.alsbruch.checked)
	{
		for(i=0;i<l.length;i++)
		{
			var e=GetBruch2(l[i]);if(e=="")e=GetBruch(l[i],1e-8,10000);
			l[i]=e;
		}
	}}
	t="{"+l.join("; ")+"}";
	t=t.replace(/\./g,",").replace(/{,/,"{0,").replace(/ ,/g," 0,").replace(/-,/g,"-0,");
	return t;
}


function newton_(t,x0,n,d)
{
	
	if(String(t).indexOf("X")==-1)return NaN;
	if(x0==null)x0=Math.random()*20-10;
	var i,y,y2,yy,x=x0,T=x0+"   ";
	for(var i=0;i<=n;i++)
	{
		y=eval(t.replace(/X/g,"("+x+")"));
		if(isNaN(y))return null;
		if((Math.abs(y)<d)&&(!newtonretx)){return x;}
		y2=eval(t.replace(/X/g,"("+(x+d)+")"));
		yy=(y2-y)/d;
		x-=y/yy;
		T+=x+"   ";
	}
	return (newtonretx)?x:null;
}

function newton(t,x0,n,d)
{
	if(n==null)n=10;
	if(d==null)d=1.0e-12;
	newtonretx=true;
	return newton_(t,x0,n,d);
	newtonretx=false;
}

function Gamma(x)
{
	var g=1/x/(x+1),GG=g,G;
	
	for(var n=2;n<100000;n++)
	{
		g*=n/(x+n);
		G=g*Math.pow(n,x);
		//if(Math.abs(G-GG)<1e-10)break;
		GG=G;
	}
	return G;
}

function prim(n,nTests)
{	
		if(n==2)return true;if((n<2)||(n%2==0))return false;
		if(n<=pz[pz.length-1]){for(var i=0;i<pz.length;i++)if(n==pz[i])return true;}
		var gr=Math.sqrt(pz[pz.length-1]);
		if(n<=gr){for(var i=0;(i<pz.length)&&(pz[i]<=gr);i++)if((n%pz[i])==0)return false;}
		if(n!=Math.floor(n))return false;
		if((isNaN(nTests))||(nTests==null))nTests=50;
		var pp=(1==0),k=0,q=n-1;
		do{k++;q/=2;}while((q%2)==0);
//		prompt("","1+2^"+k+"*"+q+"-"+n);
		for(var ii=0;ii<nTests;ii++)
		{
			x=Math.round(Math.floor(Math.random()*(n-2)+2));
//			alert("x="+x);
			var j=0,y=modpow(x,q,n);//prompt("","mod("+x+"^"+q+","+n+")-"+y);//return;
			pp=false;
			do
			{
				if(((j==0)&&(y==1))||(y==n-1)){pp=true;break;} //vielleicht prim
				if((j>0)&&(y==1)){break;} // sicher nicht prim
				j++;
				//prompt("",y+"^2 mod "+n);
				//alert("j="+j+"\nk="+k);
				if(j<k)y=modmult(y,y,n); else break;
				if(isNaN(y)){alert("Überlauf");return pp;}
			}while(true);
			if(pp==false)break;
		}
		return pp;
}

var pzd=new Array(1,1,2,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,7,2,3,1,5,1,3,3,2,3,3,1,5,1,2,1,6,6,2,1,2,3,1,5,3,3,3,1,3,2,1,5,7,2,1,2,7,3,5,1,2,3,4,3,3,2,3,4,2,4,5,1,5,1,3,2,3,4,2,1,2,6,4,2,4,2,3,6,1,9,3,5,3,3,1,3,5,3,3,1,3,3,2,1,6,5,1,2,3,3,1,6,2,3,4, 5,4,5,4,3,3,2,4,3,2,4,2,7,5,6,1,5,1,2,1,5,7,2,1,2,7,2,1,2,10,2,4,5,4,2,3,3,7,2,3,3,4,3,6,2,3,1,5,1,3,5,1,5,1,3,9,2,1,2,3,3,4,3,3,11,1,5,4,5,3,3,4,6,2,3,3,1,3,6,5,9,1,2,3,1,3,2,1,2,6,1,3,17,3,3,4,9,5,7,2,1,2,3,4,2,1,3,6,5,1,2,1,2,3,6,6,4,6,3,2,3,4,2,4,2,7,2,3,1,2,3,1,3,5,10,3,2,1,12,2,1,5,6,1,5,4,3,3,3,9,3,2,1,6,5,6,4,8,7,3,2,1,2,1,5,6,3,3,9,1,8,1,11,3,4,3,2,1,2,4,3,5,1,5,7,5,3,6,1,2,1,5,6,1,8,1,3,2,1,5,4,9,12,2,3,4,8,1,2,4,8,1,2,4,3,3,2,6,1,11,3,1,3,2,3,7,3,2,1,3,2,3,6,3,3,7,2,3,6,4,3,2,13,9,5,4,2,3,1,3,11,6,1,8,4,2,6,7,5,1,2,4,3,3,2,1,2,3,4,2,1,3,5,1,5,4,2,7,5,6,1,3,2,1,8,7,2,3,4,3,2,9,4,5,3,3,4,5,6,7,2,3,3,1,14,1,5,4,2,7,2,4,6,3,6,2,3,10,5,1,8,13,2,1,6,3,2,6,3,4,2,4,11,1,2,1,6,14,1,3,3,3,2,3,1,6,2,6,1,5,1,8,1,8,3,10,8,4,2,1,2,1,11,4,6,3,5,1,2,3,1,3,5,1,6,5,1,5,7,3,2,3,4,3,3,8,6,1,2,7,3,2,4,5,4,3,3,11,3,1,5,7,2,3,9,1,5,7,2,1,5,7,2,4,9,2,3,1,2,3,1,6,2,10,11,6,1,2,3,3,1,3,11,1,3,8,3,6,1,3,6,8,1,2,3,7,2,1,9,12,5,3,1,5,1,5,1,5,3,1,5,1,5,3,4,15,5,1,5,4,3,5,9,3,6,6,1,9,3,2,3,3,9,1,5,7,3,2,1,2,12,1,6,3,8,4,3,3,9,8,1,2,3,1,3,3,5,3,6,6,9,1,3,2,9,4,12,2,1,2,3,1,6,2,7,15,5,3,6,7,3,5,6,1,2,3,4,3,5,1,2,7,3,3,2,3,1,5,1,8,6,4,9,2,3,6,1,3,3,3,14,3,7,2,4,5,4,6,9,2,1,2,12,6,3,1,8,3,3,7,5,7,2,15,3,3,3,4,3,2,1,6,3,2,1,3,11,3,1,2,9,1,2,6,1,3,2,13,3,3,2,4,5,16,8,1,3,2,1,2,1,5,7,3,2,4,5,3,10,2,1,3,15,2,4,5,3,3,4,3,6,2,3,1,3,2,3,1,5,1,8,3,10,2,6,7,14,3,10,2,9,4,3,2,3,7,3,3,5,1,5,6,4,5,1,5,4,6,5,12,1,2,4,3,2,4,9,5,3,3,1,3,5,6,1,5,3,3,3,4,3,5,3,1,3,3,3,5,4,12,3,11,1,9,2,4,5,15,4,9,2,1,5,3,1,3,2,9,4,6,9,8,3,1,6,3,5,1,5,1,3,5,7,2,12,1,8,1,5,1,5,10,2,1,2,4,8,3,3,1,6,8,4,2,3,15,1,5,1,3,2,3,3,4,3,2,6,3,4,6,2,7,6,5,12,3,6,3,1,11,4,9,5,3,7,2,1,3,5,4,3,2,3,15,7,5,1,6,5,1,8,1,9,12,9,3,8,9,3,1,9,2,3,1,5,4,5,3,3,4,2,3,1,5,1,6,2,3,3,1,6,2,7,9,2,3,10,2,4,3,2,4,2,7,3,2,7,6,2,1,15,2,12,3,3,6,6,7,3,2,1,2,9,3,6,4,3,2);
var pzd2=new Array(6,1,6,15,8,1,3,11,7,3,5,6,3,1,2,4,5,3,3,12,7,3,2,4,6,9,5,1,5,1,2,3,10,3,2,7,2,1,2,7,3,6,12,5,3,4,5,1,15,2,3,1,6,2,7,3,17,6,4,3,5,1,2,10,5,4,8,1,5,7,2,1,6,3,8,3,4,2,4,2,3,4,3,3,6,3,2,3,3,4,9,2,10,2,6,1,5,3,1,5,6,1,2,10,3,15,3,2,4,5,6,3,1,14,1,3,2, 1,8,6,1,3,5,4,12,6,3,9,3,2,7,3,2,6,4,3,6,2,3,6,3,6,1,8,10,2,1,5,9,4,2,7,2,1,3,11,3,7,3,3,5,3,1,5,1,2,1,11,1,2,3,3,6,3,7,5,6,3,4,2,18,7,6,3,2,3,1,6,3,6,8,1,5,4,11,1,6,3,2,3,9,1,6,3,2,6,4,3,6,2,3,6,3,1,6,6,2,7,3,8,3,1,5,4,9,3,17,1,14,1,11,3,1,5,6,1,3,2,4,11,3,1,5,4,2,3,4,2,6,9,6,10,2,3,3,4,2,1,8,6,1,5,4,5,1,2,3,7,6,11,4,14,1,2,10,2,1,2,7,5,6,1,6,8,1,14,4,11,4,2,3,3,7,2,4,6,3,3,2,10,2,9,1,6,3,2,3,7,9,5,4,5,16,3,5,3,3,1,3,8,3,1,6,3,14,1,5,4,8,3,4,3,5,12,10,5,1,5,1,6,2,3,10,2,1,6,9,5,1,5,1,2,10,8,13,2,4,3,2,6,3,4,6,6,3,2,4,11,1,8,7,5,3,6,6,7,3,2,10,2,6,3,1,3,3,8,4,11,1,14,4,3,2,10,2,6,12,10,2,4,5,1,8,1,6,6,17,1,2,3,6,3,3,4,3,2,1,3,12,2,10,5,3,3,7,2,3,3,1,6,3,5,1,5,3,10,2,13,2,1,3,11,1,12,2,3,1,2,3,12,3,4,2,1,17,3,4,8,6,1,5,1,5,3,4,2,4,6,11,3,7,2,13,2,1,6,5,4,2,4,6,2,7,3,8,3,4,2,3,3,4,3,5,6,1,3,3,8,4,3);
pzd3=new Array(3,6,5,1,3,9,2,3,3,3,6,9,4,3,5,4,9,2,7,3,9,5,4,5,6,1,3,6,6,18,2,3,4,2,3,1,2,9,6,3,4,3,3,2,9,1,2,1,12,2,3,3,7,15,3,2,3,6,3,10,2,4,2,4,3,3,2,15,1,5,6,4,5,4,12,3,6,2,7,2,3,1,14,7,8,1,6,3,2,10,5,3,3,3,4,5,6,7,5,7,8,7,5,7,3,8,3,4,3,8,10,5,1,3,2,1,2,6,1,5, 1,3,11,3,1,2,9,4,5,4,11,1,5,9,7,2,1,2,9,1,2,3,4,5,1,15,2,15,1,5,1,9,2,9,3,7,5,1,2,10,18,3,2,3,7,2,10,5,7,11,3,1,15,6,5,9,1,2,7,3,11,9,1,6,3,2,4,2,4,3,5,1,6,9,5,7,8,7,2,3,3,1,3,2,1,14,1,14,3,1,2,3,7,2,6,7,8,7,2,3,4,3,2,3,3,3,4,2,4,2,7,8,4,3,2,6,4,8,1,5,4,2,3,13,3,5,4,2,3,6,7,15,2,7,11,4,6,2,3,4,5,3,7,5,3,1,5,6,6,7,3,3,9,5,3,4,9,2,3,1,3,5,1,5,4,3,3,5,1,9,5,1,6,2,3,4,5,6,7,6,2,4,5,3,3,10,2,7,8,7,5,4,5,6,1,9,3,6,5,6,1,2,1,6,3,2,4,2,22,2,1,2,1,5,6,3,3,7,2,3,3,3,4,3,18,9,2,3,1,6,3,3,3,2,7,11,6,1,9,5,3,13,12,2,1,2,1,2,7,2,3,3,4,8,6,1,21,2,1,2,12,3,3,1,9,2,7,3,14,9,7,3,5,6,1,3,6,15,3,2,3,3,7,2,1,12,2,3,3,13,5,9,3,4,3,3,15,2,6,6,1,8,1,3,2,6,9,1,3,2,13,6,3,6,2,12,12,6,3,1,6,14,4,2,3,6,1,9,3,2,3,3,10,8,1,3,3,9,5,3,1,2,4,3,3,12,8,3,4,5,3,7,11,4,8,3,1,6,2,1,11,4,9,17,1,3,9,2,3,3,4,5,4,9,3,2,1,2,4,8);
pzd=pzd.concat(pzd2).concat(pzd3);
var pz=new Array(2+pzd.length);pz[0]=2;pz[1]=3;
for(var i=0;i<pzd.length;i++)pz[i+2]=pz[i+1]+pzd[i]*2;
pdz=pdz2=pzd3=null;

function faktor(n)
{
	if(n==1)return "1";
	if(n<1)return "?";
	if((n%1)!=0)return "?";
	if(n>=281474976710656){return "Die Zahl ist zu groß";}
	var i,t=new Array(),g=Math.sqrt(n)+1,j,bb=(1==0);
	for(i=0;(i<pz.length)&&(n>1);i++)
	{
		bb=false;
		while(((n%pz[i])==0)&&(n>1)){t[t.length]=pz[i];n/=pz[i];bb=true;}
		if(bb)
		{
			g=Math.sqrt(n)+1;
		}
		if((n>1)&&(pz[i]>g)){t[t.length]=n;n=1;break;}
	}
	i=pz[pz.length-1];
	while(n>1)
	{
		i+=2;
		g=Math.sqrt(i)+1;
		for(j=0;(pz[j]<=g)&&(j<pz.length);j++)if((i%pz[j])==0)break;
		if(pz[j]>g)
		{
			pz[pz.length]=i;
			while(((n%pz[pz.length-1])==0)&&(n>1)){t[t.length]=pz[pz.length-1];n/=pz[pz.length-1];}
			//if(prim(n))return t.join("·");
		}
		if(i>30000)break;
	}
	if(n>1)t=t.concat(faktorRho(n));
	return t.join("·");
}
function factor(n){return faktor(n);}
function faktorRho(n)
{
	var x, xx, k, L, m, g,N=n,j=0,i=0;
	var nt=0,t=new Array();
	if(n>=281474976710656){t[0]=n+" ist zu groß";return t;}
	x=5;xx=2;k=1;L=1;m=N;
	while((N%2)==0){N/=2;t[nt++]=2;}
	while((N%3)==0){N/=3;t[nt++]=3;}
	while((N%5)==0){N/=5;t[nt++]=5;}
    	do
	{
		if (prim(N,25))
		{
			t[nt++]=N;//alert("gefunden: "+N);
			return t;
		}
        	do
		{
		     	g = ggT(N,Math.abs(x-xx));
			if(g!=1) break;
			if(isNaN(g)){t[nt++]="Fehler";return t;}
			k--;
			if(k==0){xx=x;L=L*2;k=L;}
            	//x *= x; x++; x%=N;
			x=modmult(x+1,x-1,N);
			if(isNaN(x)){t[nt++]="Fehler";return t;}
            }while(true);
		t[nt++]=g;//alert("gefunden: "+g);
		if(g==N){alert ("Fehler");return t;}
		N /= g;
		x %= N;
		xx %= N;
		i++;
	}while(i<10000);
	t[nt++]=N+" (möglicherweise keine Primzahl)";
	return t;
}

function primzahl(n,m)
{	
	n=Math.floor(n);if(isNaN(m))m=10000;
	if((Math.abs(n)<2)||(n==-2)||(n==-3))return 2;
	var v=(n<0)?-1:1,mm=0;
	n=Math.round(v*(n+1-n%2));
	while((prim(n,15)==0)&&(mm<m)){n=Math.round(n+v*2);mm++;}
	if(m==mm){alert("Nach "+mm+" Versuchen keine Primzahl gefunden\nAbbruch");return "-1";}
	return Math.round(n);
}

var binaer=new Array(32);binaer[0]=1;
for(var i=1;i<binaer.length;i++)binaer[i]=binaer[i-1]<<1; 

function modpow(b,e,m)
{
	if(e==0)return 1;
	var i, L=1,t="";
	var p=1,a=(1==0);
	b%=m;
	p=b;
	var bin=new Array(),ee=e;
	i=0;
	while(ee>0){bin[i++]=ee%2;ee=Math.floor(ee/2);}
	for(i=bin.length-1;i>=0;i--)ee=ee*2+bin[i];
	//alert(bin+"\n"+e+"\n"+ee);
	for(i=bin.length-2;i>=0;i--)
	{
		p=modmult(p,p,m);	//t+=p+"\n";
		if(bin[i]>0.5){p=modmult(p,b,m);t+=p+"\n";}
		//alert("e="+e+"\ni="+i+"\n"+bin[i]+"\np="+p);
	}
//	document.f.tester.value=t;
	return p;
}

function modmult(f1,f2,m)
{
	f1%=m;f2%=m;
//	var t="MOD("+f1+"*"+f2+","+m+")-";
	var M=100000;
	if(m<M)return (f1*f2)%m;
	if(m>M)return modmult2(f1,f2,m);
	var A=String(f1),B=String(f2);
	var L1=A.length,L2=B.length;
	A="000000000000000000000".substr(0,18-L1)+A;
	B="000000000000000000000".substr(0,18-L2)+B;
	var a3=Number(A.substr(0,6)),a2=Number(A.substring(6,12)),a1=Number(A.substring(12,18));
	var b3=Number(B.substr(0,6)),b2=Number(B.substring(6,12)),b1=Number(B.substring(12,18));
	var q=M%m,q2=(q*q)%m,q3=(q*q2)%m,q4=(q3*q)%m;
	//prompt("",t+((a1*b1)%m + (q*((a1*b2)%m + (a2*b1)%m))%m + (q2*(a2*b2)%m)%m )%m);
	//return ((a1*b1)%m + (q*((a1*b2)%m + (a2*b1)%m))%m + (q2*(a2*b2)%m)%m )%m;
	var s=(a1*b1)%m;
	var s1=((a1*b2)%m) + ((a2*b1)%m);
	s1=(s1*q)%m;
	s=(s+s1)%m;
	s1=(((a1*b3)%m) + ((a2*b2)%m) +((a3*b1)%m))%m;
	s1=(s1*q2)%m;
	s=(s+s1)%m;
	s1=(((a2*b3)%m) + ((a3*b2)%m))%m;
	s1=(s1*q3)%m;
	s=(s+s1)%m;
	s1=(a3*b3)%m;
	s1=(s1*q4)%m;
	s=(s+s1)%m;
//	prompt((a3+" "+a2+" "+a1)+"   "+(b3+" "+b2+" "+b1),t+s);
	return s;
}

function Teiler(N)
{
	if(N==1)return "{1}";
	var f=faktor(N).split("·");
	var prf=new Array(),prfn=new Array(),i,j;
	prf[0]=f[0];prfn[0]=1;j=0;
	for(i=1;i<f.length;i++){if(prf[j]==f[i]){prfn[j]++;continue;}prf[++j]=f[i];prfn[j]=1;}
	var n=prfn[0]+1;for(i=1;i<prf.length;i++)n*=(prfn[i]+1);
	T=new Array(n);
	for(i=0;i<n;i++)T[i]=1;
	var k=prfn[0]+1;
	var p=prf[0];
	var pp=1;
	for(i=0;i<prfn[0];i++){pp*=p;T[i+1]=pp;}
	for(i=1;i<prf.length;i++) //Schleife über alle Primfaktoren
	{
		p=prf[i];pp=p;
		for(j=0;j<prfn[i];j++) //Schleife über alle Potenzen des Primfaktors
		{
			var d=j*k+k;
			for(a=0;a<k;a++){T[a+d]=T[a]*pp;}
			pp*=p;
		}
		k*=(prfn[i]+1);
	}
	quicksort(T);
	return "{"+T.join("; ")+"}";
}

function ord(b,m)
{
	var phi_=phi(m);
	var T=Teiler(phi_).replace(/\{/,"").replace(/\}/,"").replace(/ /g,"").split(";"),mp=0;
	for(i=0;i<T.length;i++)
	{
		mp=modpow(b,T[i],m);
		if(mp==1)return T[i];
	}
	return -1;
}


function check_primroot(x,p,qvec,isPrim)
{//alert(x+"  "+p+"  "+qvec+"  "+isPrim);
	if(isPrim!=true)return check_primroot_(x,p,qvec[0]);
	var i,m;
	for(i=0;i<qvec.length;i++)
	{
		m=Math.floor((p-1)/qvec[i]);
		if(modpow(x,m,p)==1)return false;
	}
	return true;
}

function check_primroot_(x,p,Phi)
{
	var i,m=1,k,t=" ";
	for(i=1;i<=Phi;i++)
	{
		m*=x;
		m%=p;
		if(t.indexOf(" "+m+" ")>-1){return false;}
		t+=m+" ";
	}
	return true;
}


function check_primroot__(x,p,Phi)
{
	var f=factor_vec(p);
	for(var i=0;i<f.length;i++)
	{
		if(!check_primroot(x,f[i],factor_vec(f[i]-1),true)) return false;
	}
	return true;
}

function factor_vec(x)
{	
	var t=faktor(x).split("·");
	var f=new Array(),j=0;
	f[0]=t[0];
	for(var i=1;i<t.length;i++)if(t[i]!=f[j])f[++j]=t[i];
	return f;
}

function isPrimroot(r,p)
{
	var Phi=phi(p);
	if(Phi==p-1)
	return check_primroot(r,p,factor_vec(Phi),true);
	var A=new Array(1);A[0]=Phi;
	return check_primroot(r,p,A,false);
}

function primroot(p)
{
	var x=2,w=2,s,qvec=new Array();
	var Phi=phi(p),ip=(Phi==p-1);
	if(ip)qvec=factor_vec(Phi);else {qvec[0]=Phi;if(p>10000){alert("Die Primitivwurzelberechnung für nichtprime Modulen ist beschränkt bis 10000.");return "?";}}
	while(x<=p-1)
	{
		if(!ip)while(ggT(x,p)!=1)x++;
		if(check_primroot(x,p,qvec,ip))return x;
		x++;
		while((s=w*w)<x)w++;
            if(s==x)x++;
	}
	return "";
}
function primroots(p,n)
{
	var x=2,w=2,s,qvec=new Array(),T=new Array();
	var Phi=phi(p),ip=(Phi==p-1);
	if(ip)qvec=factor_vec(Phi);else {qvec[0]=Phi;if(p>1000){alert("Die Berechnung aller Primitivwurzeln für nichtprime Modulen ist beschränkt bis 1000.");return "?";}}
	if((isNaN(n))||(n<1))n=p;
	while(x<p)
	{
		if(!ip)while(ggT(x,p)!=1)x++;
		if(check_primroot(x,p,qvec,ip)){T[T.length]=x;if(T.length>=n)break;}
		x++;
		while((s=w*w)<x)w++;
            if(s==x)x++;
	}
	return "{"+T.join("; ")+"}";
}

function jacobi(x,y)
{
	var m8,temp,res=1;
	if((y<3)||((y%2)==0))return 0;
	while(true)
	{
		x%=y;
		if(x==0)return 0;
		while((x%2)==0)
		{
			x=Math.floor(x/2);
			m8=y%8;
			if((m8==3)||(m8==5))res=-res;
		}
		if(x==1)return res;
		temp=x;x=y;y=temp;
		if(((x%4)==3)&&((y%4)==3))res=-res;
	}
}

function phi(n)
{
	if(n==1)return 1;
	var fz=faktor(n).split("·"),p=fz[0]-1,i;
	for(i=1;i<fz.length;i++){if(fz[i]==fz[i-1])p*=fz[i];else p*=fz[i]-1;}
	return p;
}

function modpow____(x,n,m)
{
    	var y=1,z=x,nn=n,r;
    	do
	{
        	r = n%2;
        	n=(n-r)/2;
        	if(r==1)
		{
            	y = (z%m)*(y%m) % m;
			if(isNaN(y)){alert("Überlauf");return -1;}
            	if(n==0)return y;
		}
		z = z % m;
		z = (z*z)% m;
		if(isNaN(z)){alert("Überlauf");return -1;}
    	}while(true);
}

function fib(n)
{
	if((n<1)||(Math.floor(n)!=n))return "Fehler";
	if(n<3)return 1;var a=1,b=1,c;
	for(i=1;i<n-1;i++){c=a+b;a=b;b=c;}
	return c;
}

function sin(x){return Math.sin(x*grad_rad);}
function cos(x){return Math.cos(x*grad_rad);}
function tan(x){return Math.tan(x*grad_rad);}
function asin(x){return Math.asin(x)*rad_grad;}
function acos(x){return Math.acos(x)*rad_grad;}
function atn(x){return atan(x);}
function atan(x){return Math.atan(x)*rad_grad;}
function logY(x,y){return Math.log(x)/Math.log(y);}
function log2(x){return Math.log(x)/Math.log(2);}
function log10(x){return Math.log(x)/Math.log(10);}
function harM(x,y){return 2/(1/x+1/y);}
function geoM(x,y){return Math.sqrt(x*y);}
function sgn(x){return (x>0)?1:(x==0)?0:-1;}
function cent(x){return logY(x,2)*1200;}
function sv(x){return Math.pow(2,(x/1200));}
function frac(x){return Math.abs(x)-Math.floor(Math.abs(x));}
function ggT3(a,b,c){return ggT(ggT(a,b),c);}
function ggT4(a,b,c,d){return ggT(ggT(a,b),ggT(d,c));}
function ggT5(a,b,c,d,e){return ggT(ggT3(a,b,c),ggT(d,e));}
function ggT6(a,b,c,d,e,f){return ggT(ggT3(a,b,c),ggT(d,e,f));}
function kgV3(a,b,c){return kgV(kgV(a,b),c);}
function kgV4(a,b,c,d){return kgV(kgV(a,b),kgV(d,c));}
function kgV5(a,b,c,d,e){return kgV(kgV3(a,b,c),kgV(d,e));}
function kgV6(a,b,c,d,e,f){return kgV(kgV3(a,b,c),kgV3(d,e,f));}
function cot(z){return cos(z)/sin(z);}
function sec(z){return 1/cos(z);}
function csc(z){return 1/sin(z);}
function acot(z){return Math.PI/2*rad_grad-atan(z);}
function asec(z){return acos(1/z);}
function acsc(z){return asin(1/z);}
function sinh(x){x*=grad_rad; return (Math.exp(x)-Math.exp(-x))/2 ;}
function cosh(x){x*=grad_rad; return (Math.exp(x)+Math.exp(-x))/2 ;}
function tanh(x){x*=grad_rad; return (Math.exp(2*x)-1)/(Math.exp(2*x)+1) ;}
function coth(z){return 1/tanh(z) ;}
function sech(z){z*=grad_rad; return 2*Math.exp(z)/(Math.exp(2*z)+1) ;}
function csch(z){z*=grad_rad; return 2*Math.exp(z)/(Math.exp(2*z)-1) ;}
function asinh(x){return rad_grad*Math.log(Math.sqrt(x*x+1)+x) ;}
function acosh(x){return rad_grad*Math.log(Math.sqrt(x*x-1)+x) ;}
function atanh(x){return rad_grad*((Math.log(x+1)-Math.log(1-x))/2) ;}
function acoth(z){return rad_grad*Math.log((z+1)/(z-1))/2 ;} 
function asech(z){return rad_grad*Math.log((Math.sqrt(-z*z+1)+1)/z) ;}
function acsch(z){return rad_grad*Math.log((sgn(z)*Math.sqrt(z*z+1)+1)/z) ;}
function fresnels(x){return FresnelS(x);}
function fresnelc(x){return FresnelC(x);}
function FresnelS(x)
{
	var x3=x*x*x,x4=x3*x;
	return -x3*(((((((3933*x4-948290)*x4+173660760)*x4-23124301200)*x4+2108936269440)*x4-120784531795200)*x4+3.796085284992E+15)*x4-5.3145193989888E+16)/1.59435581969664E+17;
}
function FresnelC(x)
{
	var x2=x*x,x4=x2*x2;
	return x*((((((((x4/690452066304000-1/2528170444800)*x4+1/11975040000)*x4-1/76204800)*x4+1/685440)*x4-1/9360)*x4+1/216)*x4-1/10)*x4+1);
}