Berechnung von Primzahlen

xindon

Verwirr den armen Jungen nich :))

Christoph K. schrieb:

Und wieso verwendest du hier einen Vektor?

Moin,

hatte keinen besonderen Grund, ich fand es halt am übersichtlichsten. Hätte auch mit new und delete nen dynamisches Array machen können. Keine Ahnung ob das großartig schneller wäre, is aber mal ne interessante Frage. Ich habe auch erst vor ein paar Wochen mit C++ angefangen und spiele damit jeden Tag ein bissle rum. Bis ich das alles so halbwegs kann wird noch ne ganze Weile ins Land gehen.

Gruß Chris

CStoll

Christoph K. schrieb:

Und wieso verwendest du hier einen Vektor?

Sieb des Erasthotenes (oder so ähnlich) - damit findet man am elegantesten alle Primzahlen im Bereich von 1 bis n.

@chris: Nur zur Sicherheit solltest du am Anfang der checkPrim()-Funktion noch abfragen, ob der Vektor groß genug ist für deinen Bedarf (oder du nimmst gleich a.size() als Obergrenze).

Jester

justchris schrieb:

Nabend, hab Dir mit den Codeschnipseln hier und einer schnelleren Primzahlfindefunktion mal was zusammengebastelt, hoffe es funktioniert bei dir.

Nunja, was heißt schneller. Du berechnest ja immer *alle* Primzahlen bis 30000. Auch wenn ich nur die bis 100 haben möchte.

Du könntest übrigens noch ein paar Schleifendurchläufe sparen. Wenn Du Vielfache von 2 rausgeschmissen hast, ist es nicht mehr nötig auch die Vielfachen von 4 noch rauszuwerfen.

ConstRef

for(int i=1;i<=z;i++)
  {
    if(z%i==0)
    a++;
  }

Ist es nicht sinnvoll bei (a > 1 && i < z) abzubrechen, um nicht zu viel Unnötiges zu prüfen? Finde ich zwischen 1 und z-1 mehr als eine Zahl, ist es doch keine Primzahl mehr.

Jambe66

@Cstoll
ersten mal vielen dank für die hilfe
und ich habe da noch eine frage an dich:
was bedeuted das

cout.flush();

und für was ist das l und das u in dieser funktio??

int countprim(int l,int u)
{
  int ct=0;
  for(int i=l;i<=u;++i)
    if(isprim(i)) ct++;
  return ct;
}

CStoll

Jambe66 schrieb:

was bedeuted das
cout.flush();

Das bewirkt, daß der Ausgabepuffer von cout ge"flush"t wird (die Ausgabe-Operatoren schreiben die Daten in einen Zwischenspeicher, der flush()-Befehl überträgt sie aus dem Zwischenspeicher auf den Monitor).

und für was ist das l und das u in dieser funktio??
int countprim(int l,int u)
{
  int ct=0;
  for(int i=l;i<=u;++i)
    if(isprim(i)) ct++;
  return ct;
}

l = lower, u = upper - das ist die Unter- bzw. Obergrenze des Bereiches, in dem du nach Primzahlen suchst.
(vielleicht solltest du dir die Funktionen auch mal ansehen, dann fallen dir solche Details auch auf ;))

Jester schrieb:

.Nunja, was heißt schneller. Du berechnest ja immer *alle* Primzahlen bis 30000. Auch wenn ich nur die bis 100 haben möchte.

Du könntest übrigens noch ein paar Schleifendurchläufe sparen. Wenn Du Vielfache von 2 rausgeschmissen hast, ist es nicht mehr nötig auch die Vielfachen von 4 noch rauszuwerfen.

Ja da hast du recht, wenn ich bloss prüfen soll ob ein Zahl wie 100 Prim ist, dann ist die Brute Force Methode schneller. Aber hier sollte ja ein ganzer Bereich abgedeckt werden und da is das Sieb des Eratosthenes schneller.

Man könnte es sicherlich noch weiter optimieren indem man die Vielfachen von 2 vorher rausschmeisst und nur bis Wurzel(end) prüft.

@CStoll
Stimmt meine Funktion könnte übel abstürzen, wenn nicht genug Speicher für den Vector da ist. Danke für den Tip.

justchris schrieb:

Ja da hast du recht, wenn ich bloss prüfen soll ob ein Zahl wie 100 Prim ist, dann ist die Brute Force Methode schneller. Aber hier sollte ja ein ganzer Bereich abgedeckt werden und da is das Sieb des Eratosthenes schneller.

Na ja, wenn ich sehe, dass die Siebfunktion, die ich im Netz gefunden hab, für alle Primzahlen zwischen 1 und 100.000.000 nur 1,156 Sekunden, respektive für alle zwischen 1 und 30.000 0,203 Sekunden benötigt, sehe ich gar keinen Grund eine Brute-Force Methode zu verwenden...

Jester

Eine nette Optimierung wäre zum Beispiel, das Sieb nur soweit zu berechnen, wie es auch benötigt wird.

DarthZiu

Joe_M. schrieb:

Na ja, wenn ich sehe, dass die Siebfunktion, die ich im Netz gefunden hab, für alle Primzahlen zwischen 1 und 100.000.000 nur 1,156 Sekunden, respektive für alle zwischen 1 und 30.000 0,203 Sekunden benötigt, sehe ich gar keinen Grund eine Brute-Force Methode zu verwenden...

Kannste dir vielleicht mal posten? Hab das Sieb als Dll-Funktion geschrieben und brauche für alle Primzahlen < 70000 auf nem 3 GHz Pentium 36,11 Sekunden.

Das Programm ist von Kim Walisch und gibt es inkl. Source hier: http://www.primzahlen.de

/Edit: Ich hab hier nur ein Athlon XP3200+...

Hab das Sieb als Dll-Funktion geschrieben und brauche für alle Primzahlen < 70000 auf nem 3 GHz Pentium 36,11 Sekunden.

Hmmm. Hab eine eigene Funktion auf einem Athlon XP2400 laufen.
Für alle Primzahlen < 70000 ungefähr 58 ms (Sprich Millisekunden).

und für alle Primzahlen < 700000 ungefähr 1,5 sek.

DarthZiu

Verdammt, irgendwas mach ich da wohl falsch.

DarthZiu schrieb:

Verdammt, irgendwas mach ich da wohl falsch.

Hast du die Ausgabe der Zahlen in der Berechnung drinnen ?

DarthZiu

Nein, dass würde die Berechnung ja extrem verlangsamen. Ich geb nur am Ende die größte Zahl aus.

Das is der Code:

bool *source = new bool(length);

for(int i=0; i<length; i++) {

	source[i] = true;
}

source[0] = false;
source[1] = false;

for(i=2; i<length; i++) {
	if(source[i] == true) {
		for(int j=i+1; j<length; j++) {
			if(j%i == 0)
				source[j] = false;
		}
	}
}

source[1] = true;

for(i=length; i>0; i--)
	if(source[i] == true)
	{
		printf("%d", i);
		return 0;
	}

CStoll

Also wenn du alle Primzahlen berechnen willst, bist du mit Erastotenes besser aufgehoben, anstatt für jede Zahl neu zu testen, ob sie prim ist. Wenn du nur die Größte Primzahl unter x benötigst, versuch's mal so:

int maxPrim(int x)
{
  for(;isPrim(x);--x);
  return x;
}

Meine isprim Funktion ohne Sieb:

bool isprim(int &zahl)
{
   if(zahl%2!=0)
   {
      for(int i=3;i<=sqrt(zahl);i+=2)
      {
         if(zahl%i==0)return false;
      }
   }
   else return false;
   return true;
}

crayathome schrieb:

und für alle Primzahlen < 700000 ungefähr 1,5 sek.

Auf die Gefahr hin, mich zu wiederholen: Für alle Primzahlen zwischen 1 und 100 Millionen: 1,156 Sekunden.
Die Zeit für die Primzahlen zwischen 1 und 70000: 0,203 Sekunden. Das ist zwar deutlich langsamer, als Deiner, aber der Mensch merkt keinen Unterschied zwischen 58 ms und 203 ms. Zwischen 1 Sekunde und 15 Sekunden schon (oder wie lange braucht Dein Algo für die Primzahlen < 100.000.000? ).