Berechnung von Primzahlen

Jambe66

Hi,
ich habe eine aufgabe bekommen weiß aber überhaupt net wie ich anfangen soll. kann mir einer bei dem ansatz vielleicht helfen??
die aufgabe lautet:
-ich muss ein c++ programm schreiben das zu zwei vorgegebenen positiven ganzen zahlen a und b alle primzahlen im intervall[a,b] ausgibt.
-erweitern muss ich das programm so dass es nacheinander die anzahl der primzahl in den intervallen[1,1000],[1000,2000],...,[29000,30000] ausgibt.
- ich muss zunächst eine hilfsfuntkion schreiben, die prüft, ob eine gegebene ganze zahl p eine primzahl ist. dazu muss geprüft werden ob p durch eine kleinere ganze zahl ohne rest teilbar ist.

PS: bitte nicht falsch verstehen ich möchte nicht die komplett lösung nur einen ansatz weil ich nicht weiß wie ich anfange soll.

by Jambe66

Jester

Dann fang doch erstmal klein an.

Kannst Du was schreiben, was prüft ob eine Zahl a ohne Rest durch ne Zahl b teilbar ist?

Kannst Du damit zusammen ne Funktion schreiben, die prüft ob eine gegebene Zahl prim ist?

Läßt sich das vielleicht zusammensetzen um so mehrere Zahlen zu prüfen?

akari

Hallo

dann schau dir zum Beispiel hier an was Primzahlen sind und was es für Überprüfungsvefahren gibt.

Btw : es gibt auch eine Menge Threads zum Thema Primzahlen bereits hier im Forum.

bis bald
akari

Jambe66

ich habe mal den teil des programms geschrieben wo es prüft ob es eine primzahl ist oder nicht.

#include <iostream.h>

int main()
{
    int z; // Ist diese Zahl eine Primzahl?
    int a=0; // Durch so viele Zahlen ist z teilbar
    cout << "Z: ";
    cin >> z;
    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)
        cout << "Zahl ist eine Primzahl\n";
    else
        cout << "Zahl ist keine Primzahl\n";
    return 0;

}

wie füge ich jetzt aber den rest in die funktion ein. wo genau kommt es rein??

CStoll

Du solltest diese Überpfrüfung in eine eigene Funktion auslagern:

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

(btw, es gibt effizientere Methoden, das zu überprüfen)

Jetzt kannst du z.B. in einer Schleife immer wieder diese Funktion aufrufen und auswerten:

for(i=a;i<=b;++i)
  if(isprim(i)) cout<<i<<" ";

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.