Berechnung von Primzahlen

DarthZiu

bool testPrim(int zahl)
{
    int z = zahl; // Ist diese Zahl eine Primzahl?
    int a=0; // Durch so viele Zahlen ist z teilbar
    for(int i=1;i<=z;i++) // i wird immer um 1 erhöt. Dabei wird überprüft, ob z%i==0. Wenn ja, dann wird a um eins erhöt.
    {
        if(z%i==0)
            a++;
    }

    if (a==2)
        return true;
    else
        return false;
}

/edit: Irgendwie bin ich immer zu langsam ...

Jambe66

die bool funktion kommt die vor oder nach der main funktion ?? muss ich dann noch einen prototypen in main machen?? und die for-schleife kommt in die main. ist das so richtig??

CStoll

Jambe66 schrieb:

die bool funktion kommt die vor oder nach der main funktion ??

Entweder vor die main - oder du setzt zumindest den Prototyp "bool isprim(int);" vor die main.

muss ich dann noch einen prototypen in main machen??

in der main bestimmt nicht, wenn überhaupt, dann davor (siehe oben).

und die for-schleife kommt in die main. ist das so richtig??

Wenn du deine Aufgabe in der main()-Funktion durcharbeiten willst, ist das kein Problem - aber du könntest dein Programm auch weiter strukturieren (und diese Schleife in einer anderen Funktion verstauen, die von main() aus aufgerufen wurde).

Jambe66

so als erstes mal danke für die antworten.
ich habe es jetzt aber mal so versucht:

#include <iostream.h>
//using namespace std;

int main()
{	const int MinPrimzahl=3;
    const int MaxPrimzahl=1000;
    int Primzahl, Divisor;
    bool istEinePrimzahl;
    cout << "        2" <<endl;
    for (Primzahl=MinPrimzahl; Primzahl<=MaxPrimzahl; Primzahl++)
    {
        istEinePrimzahl = true;
        // Pruefe, ob Primzahl wirklich eine Primzahl ist
        for (Divisor=2; istEinePrimzahl && Divisor<Primzahl;
             Divisor++)
        {
            // Ist das restlos teilbar?
            if (0==Primzahl % Divisor)
            {
                // Zahl ist teilbar, ist also keine Primzahl!
                istEinePrimzahl = false;
            }
        }
        // Pruefung ist beendet.
        // Wenn es eine Primzahl ist, ausgeben!
        if (istEinePrimzahl)
        {
            cout <<"        "<<  Primzahl << endl;
        }
    }
    cout << endl;
}

der gibt mir zwar die primzahlen zwischen 1 und 1000 an aber wie kann ich es machen damit ich mehrere intervalle auf einmal ausgeben kann?? wie in meinem ersten post schon gesagt muss ich die intervalle [1,1000],[1000,2000],...,[29000,30000] ausgeben können. ich habe schon versucht das ganze in eine eigene funktion zu machen(ausßerhalb von main) habs aber nicht hinbekommen.

mfg
Jambe66

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).