Prizahlberechnung - Optimierung?!

[Spike91]

Hallo,
da ich schon ziemlich lange kein Programm mehr in C++ geschrieben habe (seit 2 Jahren nicht mehr) wollte ich zur Übung eine Primzahlberechnung programmieren.
Ich habe mich für das Prinzip des "Siebes des Eratosthenes" entschieden.

Der Algorithmus zur Berechnung der Primzahlen wurde schon sehr optimiert (ist aber nicht sehr übersichtlich^^).
Es liegen allerdings noch ein paar Bugs vor, bei denen mir die Ursache nicht bekannt ist:

1. ich möchte gerne den Speicher am Ende der Funktion mit "delete []zahlen;" freigeben, was allerdings fehlschlägt.

2. die Ausgabe in die Datei nimmt die meiste Zeit des Vorganges ein.
Allerdings möchte ich keinen binären Zugriff verwenden (möchte die Daten mit einem Editor angezeigt bekommen)
Gibt es dafür eine Optimierungsmöglichkeit?

3. Primzahlen werden über die maximale Grenze mit berechnet (z.B. bei max=100 -> bis 101)

gruß
Spike

// include - Dateien:
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
#include <windows.h>

using namespace std; 

void pause();
unsigned long primzahlenSieb(unsigned long max);
void cls();
void gotoxy(int x, int y);
ofstream& dat_aus(ofstream& aus, string datname); 

int main() {
	unsigned long zahl, beginn;
	cout<<"Primzahlberechnung v2.1 by BEchecker (c) 2007"<<endl
		<<"\nmax. Primzahl: ";
	cin>>zahl;
	beginn=time(0);

	system("cls");
	cout<<"Anzahl der Primzahlen: "<<primzahlenSieb(zahl)<<endl;
	cout<<"Die Berechnung hat insgesamt "<<time(0)-beginn<<" Sekunden gebraucht!"<<endl
		<<"Grenze="<<zahl;
	pause();
	return 0;
}

void cls() {
	gotoxy(0,0);
}

void gotoxy(int x, int y) {
	COORD cur={x,y}; 
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cur); 
}

unsigned long primzahlenSieb(unsigned long max) {
	unsigned long i, j, m, anz, k;
	unsigned long per, lastPer;
	string datei("Primzahlen.txt");

	if (max%2) ++max;
	max/=2;

	bool* zahlen=new bool[max];
	anz=1;
	lastPer=0;
	per=0;

	m=sqrt(2*max);
	cout<<"Werte initialisieren...";

	for (i=2; i<=max;++i) zahlen[i]=false; // Primzahlen

	zahlen[0]=true;
	zahlen[1]=true;

	cout<<"Fertig!\n"
		<<"Primzahlen berechnen...0 %"<<endl;
	//0->1
	//1->3
	//2->5
	//3->7

	for (i=3; i<=m;i+=2) {
		j=3;

		do {
			zahlen[i*j/2]=true;	// keine Primzahl
			j+=2;
		} while (i*j/2<=max);

		per=i*100.0/m;		// Fortschritt...

		if (per>lastPer) {
			gotoxy(0,1); 
			cout<<"Primzahlen berechnen..."<<per<<" %"<<endl; 
			lastPer=per;
		}
	}

	cout<<"Primzahlen ausgeben...";

	ofstream aus;
	aus.open(datei.c_str());

	if (!aus) {
		cerr<<"Datei kann nicht geoeffnet werden! Programm wird beendet!"<<endl;
		pause();
		exit(-1);
	}

	aus<<"2, ";

	j=0;
	lastPer=0;

	for (i=0; i<=max; ++i) {
		if (!zahlen[i]) { 
			++anz; ++j;
			per=i*100.0/(double)max+1;
			if (per>lastPer) {
				gotoxy(0, 2);
				cout<<"Primzahlen ausgeben..."<<per<<" %"<<endl;
				lastPer=per;
			}
			aus<<i*2+1<<", ";
			if (j==10) { aus<<endl; j=0; }
		}
	}

	aus.close();

	return anz;
}

btw:
bin 15 Jahre alt, und programmiere hauptsächlich in VB

Zur Erklärung des Codes:
Alle Geraden zahlen werden ignoriert!
Deshalb wird am Anfang auch der Speicher nur für die Hälfte der maximalen Grenze reserviert.
Die Variablen werden initialisiert.
Dann beginnt die Berechnung (77-93).
Dabei werden alle Vielfachen ungerader Zahlen ausgesiebt, so das nur noch Zahlen übrigbleiben die nur durch sich selbst und 1 dividiert werden können (ohne Rest) (-> Primzahl)
Dann beginnt die Ausgabe...

-> Die Ausgaben auf dem Bildschirm sind die Fotschrittanzeigen...

Zeiten:

Das hier vorgestellte Programm benötig für die Berechnung der Primzahlen bis 2 Mrd 258s (auf einem zugegeben sehr schnellen Rechner incl. AUSGABE)

[Spike91]

Danke für die zahlreichen Antworten!
Durch eure vielen Tipps gelang es mir den code noch ein wenig zu verbessern!

// include - Dateien:
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <ctime>
#include <windows.h>

using namespace std; 

void pause();
unsigned long primzahlenSieb(unsigned long max);
void cls();
void gotoxy(int x, int y);

int main() {
	unsigned long zahl, beginn;

	cout<<"Primzahlberechnung v2.1 by BEchecker (c) 2007"<<endl
		<<"\nmax. Primzahl: ";
	cin>>zahl;
	beginn=time(0);
	system("cls");
	cout<<"Anzahl der Primzahlen: "<<primzahlenSieb(zahl)<<endl;
	cout<<"Die Berechnung hat insgesamt "<<time(0)-beginn<<" Sekunden gebraucht!"<<endl
		<<"Grenze="<<zahl;
	pause();
	return 0;
}

void pause() {
    cin.clear(); // Fehler-Flags löschen.
    cin.ignore(cin.rdbuf()->in_avail()); // Gepufferte Eingabe löschen.
    cin.get(); // Nächstes Zeichen einlesen.
}

void cls() {
	gotoxy(0,0);
}

void gotoxy(int x, int y) {
	COORD cur={x,y}; 
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cur); 
}

unsigned long primzahlenSieb(unsigned long max) {
	unsigned long i, j, m, anz, k;
	unsigned long per, lastPer;
	string datei("Primzahlen.txt");

	if (max%2) ++max;
	max/=2;

	bool* zahlen=new bool[max];
	anz=1;
	lastPer=0;
	per=0;

	m=sqrt(2*max);
	cout<<"Werte initialisieren...";

	for (i=2; i<max;++i) zahlen[i]=false; // Primzahlen

	zahlen[0]=true;
	zahlen[1]=false;

	cout<<"Fertig!\n"
		<<"Primzahlen berechnen...0 %"<<endl;

	//0->1
	//1->3
	//2->5
	//3->7

	for (i=3; i<=m;i+=2) {
		j=3;

		do {
			zahlen[i*j/2]=true;	// keine Primzahl
			j+=2;
		} while (i*j/2<max);

		per=i*100.0/m;		// Fortschritt...

		if (per>lastPer) {
			gotoxy(0,1); 
			cout<<"Primzahlen berechnen..."<<per<<" %"<<endl; 
			lastPer=per;
		}
	}

	cout<<"Primzahlen ausgeben...";

	ofstream aus;
	aus.open(datei.c_str());

	if (!aus) {
		cerr<<"Datei kann nicht geoeffnet werden! Programm wird beendet!"<<endl;
		pause();
		exit(-1);
	}

	aus<<"2, ";

	j=0;
	lastPer=0;

         cout<<"Ausgabe...";

	for (i=0; i<max; ++i) {
		if (!zahlen[i]) { 
			++anz; ++j;
			aus<<2*i+1<<", ";
			if (j==10) { aus<<endl; j=0; }
		}
	}

	aus.close();

	cout<<"Fertig!\nSpeicherplatz freigeben...";
	delete [] zahlen;
	cout<<"Fertig!"<<endl;

	return anz;
}

[Gregor]

Spike91 schrieb:

Danke für die zahlreichen Antworten!

Da ist ein Primzahlzählprogramm von mir. Das gibt die Zahlen nicht aus, sondern nur die Anzahl. Vielleicht kannst Du damit ja was anfangen, auch wenn es in Java ist:

public class TestPrime2
{
   public static void main (String[] args)
   {
      int end;
      if (args.length != 1)
      {
         System.out.println("Programm benötigt genau einen Parameter mit der Obergrenze.");
         return;
      }
      try
      {
         end = Integer.parseInt(args[0]);
      }
      catch(NumberFormatException e)
      {
         System.out.println("Fehler: Die Obergrenze muss ein int sein.");
         return;
      }
      long time = System.currentTimeMillis();
      int primes = countPrimes(end);
      System.out.println ("Zwischen 0 und " + end + " liegen " + primes + " Primzahlen.");
      System.out.println ("GesamtZeit : " + (System.currentTimeMillis() - time) +" ms");
   }

   private static int countPrimes(int end)
   {
      int [] sieve = new int[(end >> 6) + 1];
      int x, y;
      int primes = 1;
      int sqrt = (int)Math.sqrt((double)end);
      x = 3;
      while (x <= sqrt)
      {
         if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0)
         {
            y = x * x;
            int i = x << 1;
            ++primes;
            while (end > y)
            {
               sieve[y >> 6] |= (0x1 << ((y >> 1) & 0x1f));
               y += i;
            }
         }
         x += 2;
      }
      while (x <= end)
      {
         if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0) ++primes;
         x += 2;
      }
      return primes;
   }
}

[Spike91]

schön das doch noch einer schreibt

allerdings versteh ich nicht den gesamten code.
könntest du bitte folgende zeilen erklären?

if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0)

sieve[y >> 6] |= (0x1 << ((y >> 1) & 0x1f));

int [] sieve = new int[(end >> 6) + 1];

die Operatoren "<<" und ">>" sind mir zwar bekannt aber so richtig anfangen kann ich damit noch nichts (ich weiß nicht, was die genau bewirken)

wäre nett von dir

gruß
BEchecker

[Braunstein]

Wenn du Algorithmen willst, schau dir doch mal diesen Thread hier an
http://www.c-plusplus.net/forum/viewtopic-var-t-is-170093.html

[Werner Salomon]

Spike91 schrieb:

Der Algorithmus zur Berechnung der Primzahlen wurde schon sehr optimiert (ist aber nicht sehr übersichtlich^^).

Hallo Spike oder BEchecker,

das kann man schon noch optimieren.
1.) In der innersten Schleife schreibst Du

Spike91 schrieb:

do {
			zahlen[i*j/2]=true;	// keine Primzahl
			j+=2;
		} while (i*j/2<=max);

dort wird zweimal der Ausdruck i*j/2 berechnet. Besser ist, man tut dies nur einmal. Außerdem kann man sich die Multiplikation ganz sparen, wenn man den Index immer um 'i' erhöht. Also etwa

for( int idx = i*j/2; idx < max; idx += i )
            zahlen[idx]=true;    // keine Primzahl

2.) Man braucht mit dem Sieben einer Zahl (hier 'i') nicht bei 3*i anzufangen, sondern es reicht bei i^2 (i*i), denn alle kleineren Vielfachen von 'i' sind ja bereits durch die kleineren Zahlen weggesiebt.

for( int idx = i*i/2; idx < max; idx += i )
            zahlen[idx]=true;    // keine Primzahl

3.) Einen noch größeren Geschwindigkeitsgewinn bringt es, nicht mit allen Zahlen (bzw. mit allen ungeraden Zahlen) zu sieben, sondern nur mit allen Primzahlen. Bevor die äußere Schleife beginnt, wird zunächst im Array 'zahlen' nach der nächsten Primzahl gesucht. Das sieht dann so aus:

for( int prim = 3; (prim = (find( zahlen + prim/2, zahlen + max, false ) - zahlen)*2 + 1) <= m; prim += 2 )
    {
        for( int idx = prim*prim/2; idx < max; idx += prim )
            zahlen[idx]=true;    // keine Primzahl

        per=prim*100.0/m;        // Fortschritt...
        if (per>lastPer) {
            gotoxy(0,1);
            cout<<"Primzahlen berechnen..."<<per<<" %"<<endl;
            lastPer=per;
        }
    }

für den std::find braucht man noch einen #include <algorithm>

Mit den drei Maßnahmen zusammen sinkt die Rechenzeit für die Berechnung auf einen Bruchteil des ursprünglichen Wertes.

Spike91 schrieb:

Es liegen allerdings noch ein paar Bugs vor, bei denen mir die Ursache nicht bekannt ist:

Stimmt. Bei der Initialisierung

zahlen[0]=true;  // Idx 0 := 1; keine Primzahl
    //zahlen[1]=true; //# 3 ist eine Primzahl
    for (i=1; i<max;++i) zahlen[i]=false; // Primzahlen //# i=1 statt i=2

muss der Wert für 3 (zahlen[1]) auf false gesetzt werden, dann erscheint auch die 3.

Spike91 schrieb:

1. ich möchte gerne den Speicher am Ende der Funktion mit "delete []zahlen;" freigeben, was allerdings fehlschlägt.

das kann daran liegen, dass Du in den Schleifen über die zahlen immer auf for(i=0;i<=max;.. abfrägst. Korrekt wäre i<max, sonst wird Speicher überschrieben.

Spike91 schrieb:

2. die Ausgabe in die Datei nimmt die meiste Zeit des Vorganges ein.
Allerdings möchte ich keinen binären Zugriff verwenden (möchte die Daten mit einem Editor angezeigt bekommen)
Gibt es dafür eine Optimierungsmöglichkeit?

nicht so richtig ... ich würde zunächst einfach das Komma weglassen, also die Zahlen nur mit Leerzeichen trennen. Bei der Dateigröße, mit der hier hantiert wird, spart man schon allein dadurch mehrere 10MByte.

Spike91 schrieb:

3. Primzahlen werden über die maximale Grenze mit berechnet (z.B. bei max=100 -> bis 101)

.. liegt an dem i<=max (korrekt i<max) wie oben.

Gruß
Werner

[Gregor]

Spike91 schrieb:

könntest du bitte folgende zeilen erklären?

if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0)

sieve[y >> 6] |= (0x1 << ((y >> 1) & 0x1f));

int [] sieve = new int[(end >> 6) + 1];

Ok, ich versuch es mal...

int [] sieve = new int[(end >> 6) + 1];

Ich habe eine etwas geringere Abstraktionsebene als Du: Für mich besteht das Sieb nicht aus einem Array von bools bzw. booleans in Java, sondern aus einzelnen Bits. Da Java keinen Datentyp "Bit" kennt, trickse ich da ein wenig und mache mir zu nutze, dass in Java ein int aus genau 32 Bit aufgebaut ist. Weiterhin liste ich in meinem Sieb nur die ungeraden Zahlen auf, denn gerade Primzahlen gibt es neben der 2 nicht. Ich kann also in jedem int ein Interval von 64 Zahlen betrachten. Deshalb benötigt mein int-Array nur ein 64-tel an Elementen gegenüber einem boolschen Array. Ein Shift um 6 nach rechts, das ist das ">> 6" entspricht dabei genau einer Division durch 64. Mit anderen Worten: In dieser Zeile wird praktisch das Sieb mit der erforderlichen Anzahl an Einträgen erstellt. Die +1 erhöht die Länge des Arrays nochmal um 1. Ich bin mir aber nicht mehr ganz sicher, welche Überlegung da damals dahinterstand.

Entsprechend zu dem hier auftretenden Shift sind auch die anderen Bitshifts um 6 nach rechts zu sehen. Es geht dabei jeweils darum, den passenden int aus dem Array auszuwählen.

if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0)

Hier wird festgestellt, ob die Zahl x im Sieb gestrichen wurde oder eben nicht. Also mit anderen Worten, ob x eine Primzahl ist oder nicht. Der linke Teil wurde hierbei schon erklärt: Da wird der zu x passende int aus dem Array herausgesucht. Der rechte Teil dient nun dazu, das passende Bit aus dem int auszuwählen. Hierzu wird x erstmal durch 2 geteilt "(x >> 1)", denn ich habe ja nur ungerade Zahlen abgespeichert. Als nächstes folgt eine Und-Verknüpfung mit einer Bitmaske "0x1f" = "000...00011111", die aus dem erhaltenen Wert die unteren 5 Bit ausschneidet. Der Rest interessiert nicht: Die darüberliegenden Bits dienen zur Adressierung des ints in dem Array, nur die 5 untersten Bits dienen zur Adressierung des Bits im entsprechenden int. Die reichen auch genau aus, denn 2^5=32 und es sind ja genau 32 Bit in dem int. Anschließend wird eine 1 um eben diese Adresse nach links geschiftet, damit sie praktisch genau "über" dem gewünschten Bit liegt. Mit einer Und-Verknüpfung dieser nach links geshifteten 1 mit dem int wird abschließend festgestellt, ob an dieser Stelle im int eine 0 oder eine 1 steht. Entsprechend ist da entweder eine Primzahl oder eben nicht.

sieve[y >> 6] |= (0x1 << ((y >> 1) & 0x1f));

Hier geht es jetzt ums streichen einer Zahl aus dem Sieb, um festzulegen, dass diese keine Primzahl ist. Der linke Teil dient wieder der Auswahl des passenden ints, der rechte Teil dient der Auswahl des passenden Bits im int. Diesmal wird das aber mit einem "|=" verknüpft. Da steht also in Wirklichkeit:

sieve[y >> 6] = sieve[y >> 6] | (0x1 << ((y >> 1) & 0x1f));

Das ist eine Oder-Verknüpfung mit anschließender Zuweisung. Das entspricht dem Streichen der Zahl y im dem Sieb.

[Spike91]

danke für eure erklärungen
vll. kann ich das programm so noch mehr optimieren

gruß
Spike91

[Spike91]

Ich habe deinen Java-Code in C++- übersetzt und ich muss sagen, dass er sehr schnell ist

Nun möchte ich mit der Funktion auch alle Primzahlen ausrechnen, was mir bislang nicht gelang:

ul - unsigned long

ul anzPrimzahlen(ul end) 
{ 
	ul *sieve = new unsigned long[(end >> 6) + 1]; 
	ul x, y; 
	ul primes = 0; 
	ul sqrta = (unsigned long)sqrt((double)end); 

	for (x=0;x<((end >> 6) + 1); ++x) sieve[x]=0;
	cout<<"Primzahlen berechnen...";
	x = 3; 
	while (x <= sqrta) 
	{ 
	 if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0) 
	 { 
		y = x * x; 
		unsigned long i = x << 1; 
		while (end > y) 
		{ 
		   sieve[y >> 6] |= (0x1 << ((y >> 1) & 0x1f)); 
		   y += i; 
		} 
	 } 
	 x += 2; 
	} 

	x=1;

	while (x <= end) 
	{ 
		if ((sieve[x >> 6] & (0x1 << ((x >> 1) & 0x1f))) == 0) {
			++primes; 
			cout<<(((x >> 6)+(x >> 1))*2+1)<<" ";
			if (!(primes%10)) cout<<endl;
		x += 2; 
	} 

	delete [] sieve;

	cout<<"Fertig!"<<endl;
	return primes; 
}

habt ihr eine Idee??

gruß
Spike91

[CStoll]

Dazu mußt du nur statt der "++primes;" Anweisung in der unteren Schleife ein (ungetestet) "cout<<x;" einsetzen.

[Spike91]

Es ging mir eher um das Prinzip, die Primzahlen durch
solche Anweisungen ( z.b. cout<<(((x >> 6)+(x >> 1))*2+1)<<" "; )
herauszufinden....(um den code besser zu verstehen )

(hab mich vll. schlecht ausgedrückt^^)

trotzdem danke, für die zahlreichen Tipps

gruß
Spike

[CStoll]

Wenn ich den Code richtig interpretiere, bildet das Programm (genauer - die Schleife while(x<=sqrta)... das Sieb des Eratosthenes nach (und die ganzen Bit-Operationen dienen dazu, Speicherplatz zusparen, indem für jede Zahl nur ein Bit gespeichert wird).

Die zweite Schleife läuft einmal durch das fertig erzeugte Sieb und zählt die oben gefundenen Primzahlen - wenn du etwas anderes mit ihnen machen willst (z.B. ausgeben), mußt du die dortige Inkrement-Anweisung austauschen.

[Ceos]

wo ihr schon bei primzahlen seid, ist es nicht so das man eigentlich jede zahl nur versuchen muss durch vorangegangene primzahlen zu teilen ? oder gibt es zahlen die sich aus nicht-primfaktoren zusammensetzen lassen ?

[CStoll]

Technisch gesehen: Ja. Mindestens ein Teiler einer zusammengesetzten Zahl ist eine echt kleinere Primzahl.

Praktisch: Wenn du diese Tatsache ausnutzen willst, mußt du alle bisher gefundenen Primzahlen zwischenspeichern - und da mußt du einen Kompromiss zwischen Speicherbedarf (wir kontrollieren die Teilbarkeit durch alle kleineren Zahlen) und Geschwindigkeit (wir kontrollieren nur die Teilbarkeit durch Primzahlen) suchen.

[Konrad Rudolph]

Ceos schrieb:

oder gibt es zahlen die sich aus nicht-primfaktoren zusammensetzen lassen ?

Hä? Per Definition allein lautet die Antwort "nein".

http://de.wikipedia.org/wiki/Primfaktorzerlegung