// Javascripte zur Primzahlberechnung, Primfaktorzerlegung u.ä.
// (c) Arndt Brünner, 26.8.2001
// Version: 12.11.2002

p=new Array(10000);
prf=new Array(),prfn=new Array();
var nprf=0;
p[0] = 2;
p[1] = 3;
p[2] = 5;
p[3] = 7;
var np = 4;

function calcprimz(upto)
{
	upto=Math.floor(upto);
    if (upto<=p[np-1])return;
	status="Berechne Primzahlen von "+p[np-1]+" bis "+upto;
    n=0,n0=p[np-1], pp=0, b=0;
    n = p[np-1];
        do
	  {
            n += 2;
    		b=0;
            for (i = 0; i<= np; i++)
            {
                pp = p[i];
                if (n%pp == 0){b=-1; break;} //Goto 1
                if (pp * pp >= n) break;
            }
		if (b==0){ p[np] = n; np ++;status="Berechne Primzahlen von "+n0+" bis "+upto+": "+n;}
        } while (n<=upto);
	if(document.ff!=null)document.ff.ubound.value=" Es sind momentan "+np+" Primzahlen gespeichert: 2 ... "+ p[np-1];
	status= np+" Primzahlen gespeichert: 2 ... "+ p[np-1]
}

function isprim(n)
{
	if (n==2) return 2;
	if (n==1) return 0;
	if (n%2==0) return 0;
	for (i=0;i<np;i++)
	{
		if (n==p[i]) return n;
		if (n%p[i]==0) return 0;
	}
	nnp=np
      calcprimz(Math.sqrt(n));
      for (i = nnp; i<= np; i++)
      {
          if (n%p[i] == 0){return 0;}
      }
      return n;
}

function getprz(von,bis,sep)
{
      if ((bis==0)||(bis<2)||(von>bis)) return "fehlerhafte Eingaben können nicht bearbeitet werden";
	if ((bis>p[np-1])&&(von>p[np-1])&&(document.f.fast.checked==true)) return getprimzfast(von,bis,sep);
	if (bis>p[np-1]) calcprimz(bis);
	for (i=0;i<np;i++) if (p[i]>=von) break;
      j=i-1;
      do
	{
            j++;
	}while(p[j]<=bis);
	t=p.slice(i,j);
	return t.length+" Primzahlen zwischen "+von+" und "+bis+" gefunden:\n"+t.join(sep);
}

function getprimzfast(von,bis,sep)
{
	t=new Array();
	z=0;
	if (bis*bis>p[np-1]) calcprimz(Math.sqrt(bis)+1);
	start=von-von%2+1;
	if (von<p[np-1])
	{
		for (i=0;i<np;i++) if (p[i]>=von) break;
		t=p.slice(i,np); 
		start=p[np-1]+2;
	}
	for (n=start;n<=bis;n+=2)
	{
		g=Math.sqrt(n)+1;
		i=1; b=1;
	      while (p[i]<g)
      	{
          		if (n%p[i] == 0) {b=0;break;}
			i++;
	      }
            if (b==1){t[t.length]=n;}
	}
	return t.length+" Primzahlen zwischen "+von+" und "+bis+" gefunden:\n"+t.join(sep);
}

function primfz(n,useapplet,applet)
{
	var nn=String(n);
	if (Number(n)<2)return "";
	t=new String("");
	if((useapplet==true)&&(applet!=null))
	{
		t=String(applet.faktor(nn,"·",60));
		var A=t.split("·");
		for(i=0;i<A.length;i++)
		{AA=A[i];A[i]=Number(AA);
		if( (String(A[i]).indexOf("e")>-1) || (String(A[i]).substr(String(A[i]).length-1,1)!=AA.substr(AA.length-1,1)))A[i]=AA;}
		quicksort(A);
		t=A.join("·");
	}
	else if((useapplet==true)&&(applet==null))
	{
		var A=faktorRho(nn);
		quicksort(A);
		t=A.join("·");
	}
	else
	{
	n=Number(n);
	i=0;
	for (i=0;i<np;i++)
		while (n%p[i]==0) {t+=p[i]+"·";n/=p[i];if(n==1) break;}
	if (n>1)
	{
		calcprimz(Math.sqrt(n+2));
		for (j=i+1;j<np;j++)
			while (n%p[j]==0) {t+=p[j]+"·";n/=p[j];if(n==1) break;}
	}
	if (n>1) t+=n+" ";
	t=t.substr(0,t.length-1);
	}
	pf=t.split("·"); //Erzeugen der Felder mit Primfaktoren zur Teilerfindung
	prf[0]=pf[0];prfn[0]=1;nprf=0;
	for(i=1;i<pf.length;i++)if(pf[i]==prf[nprf])prfn[nprf]++; else {prf[++nprf]=pf[i];prfn[nprf]=1;}
	nprf++;
	return t;
}

function getTeilerSumme(T)
{
	var s=0;
	for(i=0;i<T.length-1;i++)s+=T[i];
	return s;
}

function getTeiler()
{
	var n=prfn[0]+1;for(i=1;i<nprf;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<nprf;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;
}

function quicksort(A)
{
    L=new Array(32),R=new Array(32);
    var s, i, j, LL, rr, v, w, ii;
    s=0; L[0]=0; R[0]=A.length-1;
    do
    {
        LL = L[s]; rr = R[s];
        s--;
        do
        {
            i = LL; j = rr;
            v = A[Math.floor((LL + rr) / 2)];
            do
		{
                while(A[i]<v) i++;
                while(A[j]>v) j--;
                if (i <= j)
                {
                    w = A[i]; A[i] = A[j]; A[j] = w;
                    i++; j--;
                }
            } while (i <= j);
            if (j - LL >= rr - 1)
            {
                if (LL < j)
                {
                    s++;
                    L[s] = LL; R[s] = j;
                }
                LL = i;
            }
            else
            {
                if (i < rr)
                {
                    s++;
                    L[s] = i; R[s] = rr;
                }
                rr = j;
            }
        } while (LL < rr);
    } while (s >= 0);
}


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

function kgV(a,b)
{
    if (a*b==0) return 0;
    return a*b/ggT(a,b);
}

function calcggTkgV()
{
    var a=Number(document.f.z1.value);
    var b=Number(document.f.z2.value);
    if((a*b==0)||(isNaN(a))||(isNaN(b)))
        document.f.ggTkgV.value="";
    else
	  document.f.ggTkgV.value="ggT = "+ggT(a,b)+"\nkgV = "+kgV(a,b);
}

function calcggTkgV2()
{
	document.f.ggTkgV.value="";
	var t=document.f.z3.value;if(t=="")return;
	t=t.replace(/\D/g,",").replace(/,+/g,",");
	while(t.charAt(0)==",")t=t.substr(1,t.length-1);
	while(t.charAt(t.length-1)==",")t=t.substr(0,t.length-1);
	var A=t.split(","),i=0;
	for(i=0;i<A.length;i++)A[i]=Number(A[i]);
	var g=A[0],k=g,gg=g;
	for(i=1;i<A.length;i++)
	{
		gg=ggT(A[i],gg);
		g=ggT(A[i],k);
            k*=A[i]/g;
      }
	document.f.ggTkgV2.value="ggT = "+gg+"\nkgV = "+k;
}

function goldbach(n)
{
	if(isNaN(n))return "";
	if(n%2==1)return n+" ist ungerade";
	nh=n/2;j=-1;
	var proba=false,ipp=0;
	for(i=0;i<np-1;i++)if(p[i]>=nh){j=i;break;}
	if(j==-1)
	{
		if(p[np-1]+1000<n/2)
		{
			j1=n/2;j2=j1;if(j1%2==0){j1--;j2++;}
			while((ipp=isprobaprim(j1))==0)j1-=2;
			if(ipp==-1)return"Zahl ist zu groß";
			while((ipp=isprobaprim(j2))==0)j2+=2;
			if(ipp==-1)return"Zahl ist zu groß";
			do
			{	
				s=j1+j2;
				window.status=j1+" + "+j2+" = "+s;
				if(s==n)return j1+" + "+j2;
				if(s>n){j1-=2;while((ipp=isprobaprim(j1))==0){if(ipp==-1)return"Zahl ist zu groß"; j1-=2; if(j1<3)return "kein Paar gefunden!";}}
				else{j2+=2;while((ipp=isprobaprim(j2))==0){if(ipp==-1)return"Zahl ist zu groß";j2+=2; if(j2>n)return "kein Paar gefunden!";}}
			}while(true);
			return "?";
		}
		else
		{calcprimz(n/2+100);for(i=0;i<np;i++)if(p[i]>=nh){j=i;break;}}
	}
	j0=j;j1=j;z=0;na=np*2;prot="";
	do
	{
		s=p[j0]+p[j1];prot+=s+" ";
		if(s==n)return p[j0]+" + "+p[j1];
		if(s>n){j0--;if(j0<0)return "kein Paar gefunden!";}
		else{j1++;if(p[j1]>n)return "kein Paar gefunden!";if(j1>np){calcprimz(p[np-1]+100);na=np*2;}}
		z++;if(z>=na){alert(prot);return "Abbruch "+z;}
	}while(true);
	return "?";
}

function euler_phi(p)
{
	if(p>0)primfz(p,true,null);var e=1.0;
	for(i=0;i<nprf;i++)for(j=0;j<prfn[i];j++){if(j==0)e*=(prf[i]-1);else e*=(prf[i]);}
	return e;
}

function invers(a,m)
{
	var r=0,q=0.0,ss=1.0,s=0.0,mm=m;
    	do{q=Math.floor(a/m);r=a-q*m;sss=s;s=ss-q*s;ss=sss;a=m;m=r;}while(r>0)
    	if(ss<0)ss+=mm;
	return ss;
}

function isprobaprim___(n,ntests)
{	
		var nTests=(Number(ntests)>0)?ntests:100;
		if(document.primtestapplet!=null)return ((document.primtestapplet.isprobaprim(n,nTests))?1:0);
		n=Number(n);
		if(n==2)return 1;if((n<2)||(n%2==0))return 0;
		if(n!=Math.floor(n))return 0;
		var pp=false,k=0,q=n-1;
		do{k++;q/=2;}while(q%2==0);//alert(n+"= n = 1 + 2^"+k+"·"+q+" = "+(1+Math.pow(2,k)*q));
		for(ii=0;ii<nTests;ii++)
		{
			x=Math.round(Math.floor(Math.random()*(n-2)/2)*2+1);
			var j=0,y=modpow(x,q,n);if(y==-1)return -1; // Zahl zu groß, Fehler bei modpow
 			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++;//alert(j+"  "+k);
				if(j<k)y=(y*y)%n;	else break;
			}while(true);
			if(pp==false)break;
		}
		return (pp)?1:0;
}

function mod(n,m)
{
	if((n%m)!=n-m*Math.floor(n/m))alert(n+"  "+m);
	return n-m*Math.floor(n/m);
}

var modpowX=0,modpowN=0,modpowM=0;

function modpow___(x,n,m)
{
    	var y=1,z=x,nn=n,r;
	modpowX=x,modpowN=n,modpowM=m;
    	do
	{
        	r = n%2;
        	n=Math.floor(n/2);
        	if(r==1)
		{	
			//mod(z*y,m);
			//prompt((z*y)%m,"mod("+z+" * "+y+","+m+")");
            	y = (z*y) % m;
            	if(n==0)return y;
		}
		z = z % m;
		if((z*z)/z!=z){return -1;}
		z = (z*z)% m;
    	}while(true);
}

var ord_ = new Array();

function ord(b,m)
{
	var phi=euler_phi(m),Mist="";
	primfz(phi);
	var T=getTeiler(),mp=0,i;
	for(i=0;i<T.length;i++)
	{
		mp=modpow(b,T[i],m);
		if(mp==1)return T[i];
		if(mp==-1)Mist+=T[i]+"|";
	}
	ord_=Mist.substr(0,Mist.length-1).split("|");
	return -1;
}

function faktorRho___(n)
{
	var x, xx, k, L, m, g,N=n,j=0;
	var nt=0,t=new Array();
	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;}
	if(N==1)return t; 
    	do
	{
		if (isprobaprim(N,50))
		{
			t[nt++]=N;//alert("gefunden: "+N);
			return t;
		}
        	do
		{
		     	g = ggT(N,Math.abs(x-xx));
			if(g!=1) break;
			k--;
			if(k==0){xx=x;L=L*2;k=L;}
            	x *= x; x++; x%=N;
            }while(true);
		t[nt++]=g;//alert("gefunden: "+g);
		if(g==N){alert ("Fehler");return t;}
		N /= g;
		x %= N;
		xx %= N;
	}while(true);
	
}


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 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 (isprobaprim(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 isprobaprim(n,ntests)
{	
		var nTests=(Number(ntests)>0)?ntests:50;
		if(document.primtestapplet!=null)return ((document.primtestapplet.isprobaprim(n,nTests))?1:0);
		n=Number(n);
		if(n==2)return 1;if((n<2)||(n%2==0))return 0;
		if(n!=Math.floor(n))return 0;
		var pp=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=1;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 -1;}
			}while(true);
			if(pp==0)break;
		}
		return pp;
}