Primzahlen!

Wie kann ich Primzahlenb ausrechnen?

miller_m

google doch mal
http://www.google.de/search?sourceid=navclient&hl=de&ie=UTF-8&oe=UTF-8&q=primzahlen%2Bcpp
oder benutz die foren suche

durito

Gibt schon einige Beiträge im Forum dazu..

Grundsätzlich: Ausprobieren, ob die Zahl teilbar ist. D.h. beginne bei Teiler=2 und erhöhe +1 bis zur Wurzel der Zahl (weiter macht ja keinen Sinn). Wenn nie teilbar dann Primzahl...

Da gibt es aber weit effizientere Algorithmen (z.B. Sieben )

durito

*g* Optimizer am optimieren. Was meinst Du mit sieben?
Optimaler wär z.B., den Teiler nicht um +1, sondern auf die nächste Primzahl zu erhöhen.. 2, 3, 7, etc..
Und da gibts doch noch dieses "Sieb" ?.. weiss nicht mehr..

Shade Of Mine

durito schrieb:

Was meinst Du mit sieben?
Optimaler wär z.B., den Teiler nicht um +1, sondern auf die nächste Primzahl zu erhöhen.. 2, 3, 7, etc..
Und da gibts doch noch dieses "Sieb" ?.. weiss nicht mehr..

Sieb des Erathostenes, aber das ist eben für alle Primzahl in einem bestimmten Raum.

Nur durch Primzahlen dividieren ist zB unendlich schneller als die langsamer 'teste jede Zahl' Methode.

Weiters kannst du jede 2, Zahl sowieso ignorieren, das 4,6,8,10,... nie primzahlen sein können. Und schon wieder die Anzahl der benötigten Rechnungen halbiert

durito

Jo, das mein ich damit auch. Mit nem Teiler, der zwischen 2 und Wurzel(Zahl) liegt und ne Primzahl ist, testen..
Hab mal verschiedene Primzahl-Test-Funktionen geschrieben, um den VC++-Profiler anzugucken.. Macht enorm viel aus..

Shade Of Mine

durito schrieb:

Macht enorm viel aus..

Und sind IMHO ein perfektes Beispiel dafür, dass es mehr bringt den Algorithmus ansich zu optimieren, als die Implementierung desselben.

durito

Shade Of Mine schrieb:

durito schrieb:

Macht enorm viel aus..

Und sind IMHO ein perfektes Beispiel dafür, dass es mehr bringt den Algorithmus ansich zu optimieren, als die Implementierung desselben.

Kann mich dem nur anschliessen..
Wen's interessiert, hier ist ein Profiler-Output von drei Primzahlen-Funktionen (checkt, ob Zahl X ne Primzahl ist. in diesem Bsp. ist X=524287):

Func          Func+Child           Hit
        Time   %         Time      %      Count  Function
---------------------------------------------------------
      12.332  78.6       12.332  78.6        1 checkPrim_A(int) (primcheck.obj)
       3.347  21.3        3.347  21.3        1 checkPrim_B(int) (primcheck.obj)
       0.020   0.1        0.020   0.1        1 checkPrim_C(int) (primcheck.obj)

_A testet von 2 bis X Jede Zahl
_C testet jede 2. Zahl von 3 bis Wurzel(X) und 2

Macht schon ziemlich viel aus..

THX

volkard

fall meine einen interessiert:

inline bool isPrimeCheckBelow32(u32 p)
{//bei p<=6 einfach nachschauen. 
	//Das Bitmuster ersetzt ein ArrayOfBool.
	// 3         2         1         0
	//10987654321098765432109876543210
	//10100000100010100010100010101100
	return getBit(0xa08a28ac,p);//Nur die Bits 2,3,5 sind gesetzt.
};

inline bool isPrimeCheckFactorsBelow6(u32 p)
{//Teiler 2,3 und 5 mit einer Division testen
	return getBit(0x208A2882,p%30);//Nur die Bits 1,7,11... sind gesetzt.
};

inline bool isPrime(u32 p)
{
	bool isPrimeCheckFactorsAbove5(u32 p);
	if(p<32) return isPrimeCheckBelow32(p);
	if(!isPrimeCheckFactorsBelow6(p)) return false;
	return isPrimeCheckFactorsAbove5(p);
};

u32 powMod(u32 base,u32 exp,u32 modul)
{//rechnet 'base hoch exp mod modul'
	u32 a1=base,z1=exp,x=1,m=modul;
	while(z1!=0)
	{
		while((z1%2)==0)
		{
			z1/=2;
			a1=mulMod(a1,a1,m);
		};
		--z1;
		x=mulMod(x,a1,m);
	};
	return x;
};

bool isSPRP(u32 n,u32 a)
{
// Zitat: "One way to make the Fermat probable primality test more 
//	accurate is to write n-1=2sd where d is odd and s is nonnegative. 
//	Then n is a strong probable-prime base a (an a-SPRP) if either 
//	ad = 1 (mod n) or (ad)2r = -1 (mod n) for some nonnegative r 
//	less than s."
//	Quelle: http://www.utm.edu/research/primes/glossary/StrongPRP.html 
//	
//	Zitat: "Millers Test: Assume the generalized Riemann hypothesis 
//	is true. If n is an a-SPRP for all integers a with 
//	1 < a < 2(log n)2, then n is prime.
//	Quelle: http://www.utm.edu/research/primes/glossary/MillersTest.html
	u32 o=n-1;
	u32 e=findFirstBitTrue(o);
	o>>=e;
	u32 x=powMod(a,o,n);
	if(x==1) return true;
	if(x==n-1) return true;
	for(u32 i=0;i<e;++i)
	{
		x=mulMod(x,x,n);
		if(x==n-1) return true;
	};
	return false;
};

bool isPrimeCheckFactorsAbove5BySPRPCheck(u32 p)
{
// If n < 4,759,123,141 is a 2, 7, and 61-SPRP, then n is prime.
//	Quelle: http://www.utm.edu/research/primes/glossary/StrongPRP.html
//
//	Diese drei Tests reichen also, um alle Zahlen im Bereich bis 
//	2^32 zu testen. Besser sind die folgenden Zahlen, weil bis 
//	n<45559729 nur zwei Tests benötigt werden. 
//	Die Zahlen habe ich mit einem eigens dafür geschriebenen Programm 
//	gesucht. 
	if(!isSPRP(p,7252)) return false;//die 7252 deckt ab hier den größten Bereich Fehlerfrei ab
	if(p<13747) return true;//bis p<13747 ist das Ergebnis sicher
	if(!isSPRP(p,1607438)) return false;//die 1607438 deckt ab hier den größten Bereich Fehlerfrei ab
	if(p<45559729) return true;//bis p<45559729 ist das Ergebnis sicher
	if(!isSPRP(p,9786)) return false;//die 9786 deckt den Rest bis 2^32 ab
	return true;
};

namespace
{
	u32 primes[]={0,7,7*7,11,11*11,13,13*13,17,17*17,19,19*19,23,23*23,29,29*29,31,-1};
}

bool isPrimeCheckFactorsAbove5(u32 p)
{
	{//Zuerst die kleinen Teiler checken
		u32 *t=primes;
		do
		{
			if(p%*++t==0) return false;//teilt, also keine Primzahl
		}
		while(*++t<=p);
		if(*t!=-1) return true;
	}
	return isPrimeCheckFactorsAbove5BySPRPCheck(p);
};

ich vermute, die ist bei vielen zahlen noch ein wenig schneller.