Berechnung von Primzahlen

CStoll

Du hast doch oben schon die isprim()-Funktion, wieso fängst du jetzt wieder mit deinen Schleifenstrukturen an?
Und für deine Abschätzung kannst du eine weitere Funktion nehmen, die alle Primzahlen in einem Bereich zählt:

bool isprim(int z)
{
  //siehe oben
}

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

int main()
{
  for(int v=0;v<30;++v)
    cout<<"Im Bereich ["<<v*1000<<","<<(v+1)*1000<<"] gibt es "<<countprim(v*1000,(v+1)*1000)<<" Primzahlen.\n";
  cout.flush();
}

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

Gruß Chris

#include <iostream>
#include <vector>

void checkPrim(std::vector<bool>& a, int end)
{
    a[0] = true; a[1] = true;
    for (int i = 2; i <= end/2; i++)  
		for (int j = 2; j <= end/i; j++)  
			a[i*j] = true;                 
}

int countprim(int l,int u, std::vector<bool>& a)
{
  int ct=0;
  for(int i=l;i<=u;++i)
    if(!a[i]) ct++;
  return ct;
}

using namespace std;

int main(int argc, char *argv[])
{
    const int MAX_PRIME = 30000;

    vector<bool> a(MAX_PRIME+1, false);
    checkPrim(a, MAX_PRIME);    

    for(int v=0;v<30;++v)
      cout<<"Im Bereich ["<<v*1000<<","<<(v+1)*1000<<"] gibt es "<<countprim(v*1000,(v+1)*1000,a)<<" Primzahlen.\n";
    cout.flush();     

    return EXIT_SUCCESS;
}

Christoph K.

Und wieso verwendest du hier einen Vektor?

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;
	}