Primzahlenfinden mit c++

Registriert
Feb. 2005
Beiträge
518
EDIT:Neues Problem ist , dass sich "a" ab ca 9007000000000000 nicht mehr erhöht und ich weiß nicht woran das liegt.

Gelöst ist:
Ich wollte mal wissen wie ich variablen nutze die höhere Daten erlauben als 2^32 bei "int und float". Will 64bit ganaue oder noch genauere.
hab da was von "lim" LongIntegerMath gehört rechnen mit beliebig langen zahlen.

Das programiertechnische Problem ist, dass wenn ich bei meinem Primzahlenfinder bei 2^32 angelangt bin, sagt er mir ab dann jede folgende Zahl als Primzahl an.

Mein persönliches problem ist, dass dieser code zu schnell ist (viel zu effektiv programmiert!! selbstloben muss) :D und die zahlen nur so purzeln. das heißt also, dass ich noch viel höhere zahlen finden kann. aber dazu reicht mir der zahlenbereich von int und long double nicht aus.

PS:wundert euch nicht dass ich einmal cout,cin nutze und einmal printf. Bin eigentlich mit cout cin eingestiegen und habe aber in der FH gerade nur C und nicht c++ und der Prof dreht durch wenn wir c++n. Also lern ichs gerade ein wenig, immer mal.

(wers selber testen will einfach kopieren und als *.cpp speichern und dann mit c++ öffnen)


Code:
 #include <stdio.h>
#include <math.h>
#include <iostream.h>

int main ()
{
	long double a,c,d;
	_int64	 i,j;
	char e;
	do
	{
	cout<<"Primzahlen suchen zwischen (erste zahl eingeben!):";
	cin>>a;
	cout<<"           (max 2^64 = ca 9223372036,8 mrd)     und:";   //haha bis jetzt
	cin>>c;
do
{
	d=pow(a,0.5);       //pow(a,0.5) ist dabei die wurzel von a,weil weiter muss er nicht

	for(i=2;i<=d;i++) 	
            {
		j=(a/i);
		if(a==i*j)	//is die rechnung möglich kann es keine primzahl mehr sein
            goto end;	         //, also nächste zahl (goto end;)
	}
		printf("%15.0f \n",a);	
end:
	a++;
}while(a<=c);
cout<<"nochmal?J/N";
cin>>e;
	}while(e=='j'||e=='J');
	return(0);
 
Zuletzt bearbeitet:
Code:
for(j=(a/i);j<=a/i;j++)

kann sein, dass ich falsch liege, aber kann es sein, dass diese Schleife garnicht durchlaufen wird, weil dein startwert ist j= a/i und deine Abbruchbedingung ist j <= a/i gleich sind?
 
Nutz doch bitte den code-BB-Tag um Quellcode hier zu posten. So kann doch kein Mensch damit etwas anfangen.
 
Limit schrieb:
Code:
for(j=(a/i);j<=a/i;j++)

kann sein, dass ich falsch liege, aber kann es sein, dass diese Schleife garnicht durchlaufen wird, weil dein startwert ist j= a/i und deine Abbruchbedingung ist j <= a/i gleich sind?
nein da liegst du falsch. das heißt, das er genau einmal durchgehen soll (<= kleinerGLEICH). hab auch mal mit if versucht zb.: if(a%i==0) anstelle der inneren for-schleife. Da kommt aber der Fehler , dass es ein int-wert sein muss in der if-rechnung.

PS habs ma noch abgeändert.^^
 
Zuletzt bearbeitet:
Das war mein erster primzahlen-code. War aber sau lahm , also hab ich die bedingungen verschärft. und siehe da ein ultraspeed-primzahlenfinder (siehe obigen vom beitrag). Hier hab ich noch nicht mal daran gedacht dass der zahlenbereich knapp werden könnte. Kennt denn keiner "lim"? Wie kann ich den zahlenbereich anders erhöhen? mit int64? und was ist die float-variante davon? Helft mir!

Code:
#include <stdio.h>
#include <math.h>
#include <iostream.h>

void main ()
{
	long double a,c;
	unsigned int i,j,f;
	char e;
	do
	{
	cout<<"Primzahlen suchen zwischen (erste zahl eingeben!):";
	cin>>a;
	cout<<"                                              und:";
	cin>>c;
do
{
	f=0;
	for(i=2;i<=pow(a,0.5);i++)
	{
		for(j=2;j<=a/i;j++)
		{
			if(a==i*j)
			{
				f=1;
				goto end;
			}
		}
	}
	if(f==0)
	{
		printf("%15.0f \n",a);
	}
end:
	a++;
}while(a<=c);
cout<<"nochmal?J/N";
cin>>e;
	}while(e=='j'||e=='J');
}
 
Zuletzt bearbeitet:
Er wird vielleicht noch schneller, wenn Du in der for schleife nicht jedesmal eine Funktion aufrufst (pow) und das printf in der Schleife ist auch nicht gerade ein Beschleuniger :-).

D.h. Du könntest z.B. die Ergebnisse in ein Array sichern und erst am Schluss ausgeben.

Ebenso die Division in der 2. for Schleife sollte rausgezogen werden. a ändert sich doch nicht.

Bei der Zeile if f== 0 und den for Schleifen kann man die geschweiften Klammern weglassen, dann muss nicht jedesmal ein Stack aufgebaut werden.

Also Optimierungsmöglichkeiten gibt es noch viele :-).

MfG

Arnd
 
Zuletzt bearbeitet:
gute Ideen Arnd, danke dir.Habs gleich mal geändert.außer das mit dem feldern, dauert insgesammt genauso lang,denke ich zumindest sind doch genauso viele rechenschritte. aber mein hauptsächliches Problem sind die Variablentypen. int64 gibt es, wie ist der gleitkommatyp für 64bit lange vorkommastellen. will einfach über der 2^32 noch ne primzahl finden.
 
Ein printf muss das Formatfeld parsen, die Werte in ein passendes Format konvertieren.
Ausserdem muss der Wert ja noch auf der Konsole ausgegeben werden. Dazu ist normalerweise ein Interrupt nötig. D.h. es findet noch ein Taskwechsel statt.
Ingesamt ist ein printf also so ziemlich das rechenaufwendigste Teil das es gibt. Das rauszumachen wird am meisten bringen.

Für das Array brauchst Du nur viel Speicherplatz. Eine Laufvariable die hochgezählt wird und die Zuweisung auf das Array. Insgesamt also wesentlich weniger Operationen.

Bei wenigen Primzahlen wird das als Anwender wahrscheinlich nicht auffallen, bei mehreren hundert oder tausend sollte es sich sehr wohl in der Laufzeit bemerkbar machen.
Am schnellsten wird es wenn Du nicht auf die Konsole ausgibst sondern gleich in eine Datei.

Wenn du die Float und double weglässt wird es auch noch mal schneller werden.

Bzgl. der 64 Bit kann ich Dir leider keine Tipps geben.

MfG

Arnd
 
Zuletzt bearbeitet:
Nur so zur Info:
Es heißt int main() und nicht void main() ;) Und der Header ist iostream, das .h ganz schnell streichen und vergessen :) Dann musst du allerdings noch ein using namespace std; hinschreiben, da der Compiler cout und co. sonst nicht finden kann.

Zum eigentlichen Problem: Es gibt diverse Bibliotheken zum Rechnen mit großen Zahlen. Ich muss mal suchen, den Link reich ich noch nach. Bei so großen Zahlen solltest du dann aber vielleicht aber auch auf einen anderen Algorithmus umsteigen, wie z.B. das Sieb des Erathostenes.


Achso: Versuch doch mal je nach Compiler unsigned long long als Datentyp zu nehmen. Wenn das klappt, hast du schonmal 64bit Zahlen.
 
Zuletzt bearbeitet:
Fetten Dank erst mal an eure Mühen, Leute. ^^

Arnd schrieb:
Ein printf muss das Formatfeld parsen, die Werte in ein passendes Format konvertieren.
Ausserdem muss der Wert ja noch auf der Konsole ausgegeben werden. Dazu ist normalerweise ein Interrupt nötig. D.h. es findet noch ein Taskwechsel statt.
Ingesamt ist ein printf also so ziemlich das rechenaufwendigste Teil das es gibt. Das rauszumachen wird am meisten bringen.
MfG

Arnd
geht aber schnell genug

Arnd schrieb:
Für das Array brauchst Du nur viel Speicherplatz. Eine Laufvariable die hochgezählt wird und die Zuweisung auf das Array. Insgesamt also wesentlich weniger Operationen.
hast aber bei deiner rechnung die ausgabe vergessen, die dann ya nochmal extra zeit für printf braucht.also ist es im endeffekt eventuell sogar langsamer.weil bei mir rechnug-ausgaber... , bei dir rechnung feldeintrag-ausgabe uas feld..., weißt du was ich meine.ansonsten stimm ich dir voll zu.

Arnd schrieb:
Wenn du die Float und double weglässt wird es auch noch mal schneller werden.
geht leider nicht richtig wegen der pow die will kleitkommazahlen.

7H3 N4C3R schrieb:
Nur so zur Info:
Es heißt int main() und nicht void main() Und der Header ist iostream, das .h ganz schnell streichen und vergessen Dann musst du allerdings noch ein using namespace std; hinschreiben, da der Compiler cout und co. sonst nicht finden kann.
wer sagt das. es läuft spitze so. //void main () heißt aufruf hauptprogramm // in iostream.h ist cout und cin definiert, bei int main () müsste übrigens noch ein wert zurückgegeben werden, was hier nicht nötig ist. bitte drumm berichtigt zu werden, wenn ich mich irre.

7H3 N4C3R schrieb:
Zum eigentlichen Problem: Es gibt diverse Bibliotheken zum Rechnen mit großen Zahlen. Ich muss mal suchen, den Link reich ich noch nach. Bei so großen Zahlen solltest du dann aber vielleicht aber auch auf einen anderen Algorithmus umsteigen, wie z.B. das Sieb des Erathostenes.
Achso: Versuch doch mal je nach Compiler unsigned long long als Datentyp zu nehmen. Wenn das klappt, hast du schonmal 64bit Zahlen.
Ya ich frag mich halt nur welche und wie ist die syntax.wegen "unsigned long long" kommt ein error, bei "unsigned long double"gehts brauch halt noch die int64-zahlen. würd schon gern wissen wie. das Sieb des Erathostenes, klingt interesant wie geht das, ich schau ma bei wicki nach.
 
Zuletzt bearbeitet:
sebush schrieb:
wer sagt das. es läuft spitze so. //void main () heißt aufruf hauptprogramm // in iostream.h ist cout und cin definiert, also wo liegt das problem? bei int main () müsste übrigens noch ein wert zurückgegeben werde was hier nicht nötig ist.

Das sagt C++-Standard. Und der C-Standard. void main hat es nie gegeben. Es ist eine Unart, die manche Compiler durchgehen lassen, aber es ist schlichtweg falsch. Noch schlimmer ist, dass es sogar Bücher gibt, die void main schreiben. main gibt eine 0 zurück in dem Falle, dass das Programm korrekt abgelaufen ist. Du kannst das return 0 auch weglassen, dann wird es implizit angenommen.

iostream.h stammt aus der Zeit, bevor es einen C++-Standard gab. Der C++-Standard missbilligt diesen Header und bringt den neuen Header iostream mit. Dieser definiert nicht nur die IOStreams im Namensraum std, sondern enthält einige wichtige Änderungen, die mit der Verabschiedung des Standards eingeflossen sind.
 
7H3 N4C3R schrieb:
Das sagt C++-Standard. Und der C-Standard. void main hat es nie gegeben. Es ist eine Unart, die manche Compiler durchgehen lassen, aber es ist schlichtweg falsch. Noch schlimmer ist, dass es sogar Bücher gibt, die void main schreiben. main gibt eine 0 zurück in dem Falle, dass das Programm korrekt abgelaufen ist. Du kannst das return 0 auch weglassen, dann wird es implizit angenommen.

iostream.h stammt aus der Zeit, bevor es einen C++-Standard gab. Der C++-Standard missbilligt diesen Header und bringt den neuen Header iostream mit. Dieser definiert nicht nur die IOStreams im Namensraum std, sondern enthält einige wichtige Änderungen, die mit der Verabschiedung des Standards eingeflossen sind.
im krieg und beim programmieren nein in der liebe genau so wars ist alles erlaubt! wenn das richtige raus kommt. Der C++-Standard missbilligt diesen Header? wie jetzt? klappt doch alles wunderbar. erzähl mir lieber wie ich int64 inklusive einer art pow64 benutzen kann und schwaudel nicht wie ich meinen stiel ändern soll.

Haha , ich könnt feiern. ich habs. jetzt gehts bis (2^64)/2
PS: Nun gehts an den Algorythmus! Irgendwelche Vorschläge?
Code:
 #include <stdio.h>
#include <math.h>
#include <iostream.h>

int main ()
{
	long double a,c,d;
	_int64	 i,j,f;
	char e;
	do
	{
	cout<<"Primzahlen suchen zwischen (erste zahl eingeben!):";
	cin>>a;
	cout<<"           (max 2^64 = ca 9223372036,8 mrd)     und:";   //haha bis jetzt
	cin>>c;
do
{
	f=0;
	d=pow(a,0.5);
	for(i=2;i<=d;i++) //pow(a,0.5) ist dabei die wurzel von a,weil weiter muss er nicht
	{
		j=(a/i);
			if(a==i*j)		//is die rechnung möglich kann es keine primzahl mehr sein 
			{			//, also nächste zahl (goto end;)
				f=1;
				goto end;	
			}
	}
	if(f==0)			//nur wenn f null ist, ist a eine primzahl
		printf("%15.0f \n",a);	
end:
	a++;
}while(a<=c);
cout<<"nochmal?J/N";
cin>>e;
	}while(e=='j'||e=='J');
	return(0);
}
 
Zuletzt bearbeitet:
sebush schrieb:
im krieg und beim programmieren ist alles erlaubt! wenn das richtige raus kommt. Der C++-Standard missbilligt diesen Header? wie jetzt? klappt doch alles wunderbar. erzähl mir lieber wie ich int64 inklusive einer art pow64 benutzen kann und schwaudel nicht wie ich meinen stiel ändern soll.
Ich "schwaudel" nicht über deinen Stil, sondern über einen Fehler in deinem Programm. Wenn du meinst, dich nicht an den Standard halten zu müssen, weil dein Compiler dir das durchgehen lässt, ist das deine Sache. Dann kannst du dein Programm allerdings nicht mehr "gültiges C++ Programm" nennen und brauchst dich auch nicht zu wundern, wenn es auf einem anderen / neueren Compiler nicht compiliert oder etwas anderes tut. Beschwer dich später aber nicht, es hätte dir niemand gesagt. Zu iostream.h: Der Header wird missbilligt, weil er veraltet ist und nicht mehr benutzt werden soll - auch wenn er noch mit dabei ist und seinen Dienst verrichtet.

sebush schrieb:
PS: Nun gehts an den Logarythmus! Irgendwelche Vorschlge?
Ich verstehe nicht, wo du da jetzt einen Logarithmus brauchst?
 
7H3 N4C3R schrieb:
Ich verstehe nicht, wo du da jetzt einen Logarithmus brauchst?
Haha ^^, sorry. algorythmus meine ich.zb

jede Primzahl p > 3 hat die Form 6n +/- 1.

n 6n-1 6n+1

1 5 7
2 11 13
3 17 19
4 23 25
5 29 31
6 35 37
7 41 43
8 47 49
9 53 55
.... ... ... alle 5er ausgeschlossen.
PS:hab das programm mal für dich abgeändert. in int main
 
Zuletzt bearbeitet:
Ich hab mal ne Frage: Was versteht ihr unter schnell ?
Mit meinem Programm ( hab ich vor längerer Zeit mal geschrieben ) brauche ich 213 Sekunden für alle Priemzahlen bis 10.000 gebraucht. Ist das eurer Meinung nach gut ?
 
daemon777 schrieb:
Ich hab mal ne Frage: Was versteht ihr unter schnell ?
Mit meinem Programm ( hab ich vor längerer Zeit mal geschrieben ) brauche ich 213 Sekunden für alle Priemzahlen bis 10.000 gebraucht. Ist das eurer Meinung nach gut ?
nicht wirklich gut! ich schaffe gerade mit meinem Programm oben von 0 bis 100.000 in ner sekunde oder sogar schneller 6 sek bis zur million.
 
Dann hab ich zu viel schnick schnack außenrum gebastelt :D

Achso hab noch vergessen zu erwähnen, dass ich nebenbei noch jede Priemzahl in eine Datei schreibe um eine Auswertung zu haben :D
 
zwei tipps zur algorithmischen optimierung.
bei dem test der teilbarkeit brauchst du nur die primzahlen und nicht alle zahlen hochzugehen (siehe primfaktorzerlegung). wenn du die gefundenen primzahlen also in einem array zwischenspeicherst, kannst du die anzahl der divisionen drastisch reduzieren.
des weiteren brauchst du nicht alle primzahlen bis zu der zahl durchlaufen lassen, sondern kannst aufhören, wenn deine laufprimzahl größer ist, als das ergebnis der division zwischen der letzten primzahl und der zahl. dann ist deine aktuelle nämlich zwangsweise eine primzahl.

das beides dürfte massive performance vorteile bringen, wenn du größere primzahlen betrachtest.
(ich bin gerade nicht ganz sicher, aber ich glaube es gab da für größere primzahlen noch ein besseres sieb als deines, da müsste ich aber erst länger nachlesen.)
 
Zurück
Oben