Zählen der Primzahlen funzt nicht

mosquit0

Hallo,

ich sitze gerade daran die Primzahlen von 1 bis 2^16 (also 65536) zu Zählen.
Da ich danach mit den Primzahlen weiterarbeiten muss darf dabei jedoch nicht nur irgendein integer herauskommen sondern die einzelnen Zahlen müssen danach zu identifizieren sein.

Also hatte ich den Plan einfach über einen Zeiger der alle 65536 Zahlen abwandern kann die Primzahlen mit 1 und die anderen mit 0 zu markieren.

ich bin mit dem Sieb nach Erastothenes vorgegangen.

Dazu habe ich folgenden Code geschrieben:

int main(int argc, char** argv) {
    int schritt = sizeof(int);
    int i = 0;
    int j = 0;
    int Anzahl = 0;

    int *primptr = malloc (schritt*400);
    int *startptr = primptr;

    for (primptr = startptr; primptr <= primptr+(schritt*400); primptr+schritt) {
        *primptr = 0;
    } 

    for (i = 2; i <= 20; i++) {
        int flag = 0;
        primptr = startptr + i*schritt;

        if (*primptr == 0) {

        primptr = startptr;
        for (j = 2; j <= i/2; j++) {
            if (i%j == 0) {
                flag = 1;
            }
        }
        if (flag == 0) {
            primptr = primptr + i*schritt;
            while (primptr <= startptr + 400*schritt) {
                *primptr = 1;
                primptr += i*schritt;
            }

        }
        }
    }

    for (primptr = startptr; primptr <= primptr+(schritt*400); primptr+schritt) {
        if (*primptr == 1) {
            Anzahl++;
        }
    } 

    printf("%i\n", Anzahl);

    free (primptr);

    return (EXIT_SUCCESS);

wenn ich den Code anschmeisse kriege ich keinen Fehler, aber passieren tut leider auch nichts.

Kann mir jemand sagen warum ?
Danke !

volkard

a) primptr ist schon ein zeiger auf int(4bytes), daher macht ein primptr+=3 schon von alleine 12bytes weiter. hast also (außer beim malloc) das *schritt zu viel.
b) machs nicht mit zeiger, sondern mit array.

//weg
//primptr = startptr + i*schritt;
//if (*primptr == 0) {

if (startptr[i] == 0) {

Wenns dann hübsch ist, hab ich viel eher Chancen, zu erkennen, was am Verfahren falsch ist. Das ganze Zeigern verwirrt mich doch bloß.

SeppJ

Ich habe nur bis Zeile 12 gelesen, weil alles bis dahin bereits sehr merkwürdig (höflich ausgedrückt für "falsch") aussah. Du machst komische hardwarenahe Sachen, obwohl du doch eigentlich Zahlentheorie machen möchtest. Oder anders gesagt: Was haben Primzahlen mit der Größe von Integern auf deinem System zu tun?

Zudem scheinst du dir nicht bewusst zu sein, wie Zeiger überhaupt funktionieren. Du musst nicht selber die Adressen ausrechnen, das macht der Zeiger schon ganz von alleine. Stichwort: Zeigerarithmetik. Du könntest dir das alles auch sparen und einfach die Subscriptschreibweise (wie bei Arrays) benutzen: foo[i] ist kurz für *(foo+i) .

Weiterhin hast du grundlegende Schwierigkeiten bei der Konstruktion von Schleifen. Sowohl was die Syntax betrifft, als auch bei der Logik:

primptr <= primptr+(schritt*400) : Diese Laufbedingung (wenn sie so funktionieren würde, wie du das denkst. Was sie sowieso nicht tut, siehe oben) würde weiter laufen als dein reservierter Speicherbereich groß ist.
primptr+schritt : Dies macht gar nichts.

Weiter habe ich, wie gesagt, gar nicht mehr gelesen.

Wutz

Wenn du dein for korrigierst, wirst du spätestens bei Zeile 45 merken, dass dein ganzer Ansatz (Zeiger statt subscript []) falsch ist.
Die Laufzeitumgebung wird dir dies (implizit) sagen.

mosquit0 schrieb:

wenn ich den Code anschmeisse kriege ich keinen Fehler, aber passieren tut leider auch nichts.

Im aktuellen Zustand compiliert der Code gar nicht, es fehlt eine } am Ende und die Header oben. Ist schon klar, bei dir auf dem Rechner stimmt es, aber dann bitte auch den kompletten Code posten. Wenn man diese Sachen korrigiert hat schmeißt der Compiler immer noch 2 Warnungen "statement without effect", wenn er das bei dir nicht tut ist er falsch eingestellt. Für GCC: Parameter -Wall hinzufügen.

rustyoldguy

Hallo Leute!
Ist zwar C++ und sehr eingach gehalten aber die Methoden (Funktionen)
kannste vieleicht was brauchen von. Guck mal rein.

// Primelchen.cpp
// Ein Programm das Primzahlen ermittelt
// und einzelne Zahlen in ihre Primzalen zerlegt und anzeigt

#include <iostream>
using namespace std;

class primelchen
{
public:
 primelchen();
 ~primelchen();
 int primtest( unsigned long nummer);
 void teilbarkeit(unsigned long zahl);
 unsigned long Faktorentest(void); //unsigned long zahl, unsigned long (*faktoren)[100]);
 void primzahlen(void);
 void Probe (void);
 void Einzelfaktoren(void);

 private:
 unsigned long zahl, c, e, faktoren[100], kleinste, groesste, slei;
};

int main(void)
{
 primelchen primula;
 int frage = 0;

do
switch(frage)
{
 default:
         cout << endl << "Primfaktorenrechner:";
         cout << endl << "Zahl auf Faktoren prüfen....1";
         cout << endl << "Primzahlen errechnen........2";
         cout << endl << "Programm beenden............3";
         cout << endl << "\nIhre Wahl: ";
         cin >> frage;
       break;

 case 1:
     primula.Einzelfaktoren();
     frage = 0;
    break;

 case 2:
     primula.primzahlen();
     frage = 0;
    break;

 case 3:
    cout << endl << "Programmende" ; return 0;
    break;
}
while (frage != 3);

return(0);
}

/************Ende main.cpp***************************/

primelchen::primelchen()
{
 kleinste = 0;
 groesste = 100;
}; // Konstruktor
primelchen::~primelchen(){}; // Destruktor

//Prüft ob eine Zahle eine Primzahl ist oder nicht, wenn nein Rückgabe 0, wenn ja Rückgabe 1
int primelchen::primtest( unsigned long nummer)
{
unsigned long slei, a, c, e;
 e = 1;
 a = (nummer / 2) + 2;
 // Testet nummer auf Teilbarkeit durch slei nur bis kleiner nummer, da jede Zahl durch sich selbst teilbar ist
 for(slei = 2; slei < a; slei++)
     {
      c = nummer % slei;
      //cout << "nummer=" << nummer << " slei=" << slei << " c=" << c << endl;
      // Wenn nummer keine Primzahl ist, abbrechen, da weitere Überprüfung unnötig
      if((c == 0) && (slei < nummer)) { e = 0; break; }
     }

return e;
}
// Stellt fest, durch welche Zahlen das Argument "zahl" teilbar ist
void primelchen::teilbarkeit(unsigned long zahl)
{
 unsigned long slei, c, e;
  cout << endl << "Zahl teilbar durch " << endl;
    for(slei = 2; slei <= zahl; slei++)
     {
      c = zahl % slei;
      if(c == 0)
       {
        cout << slei << "  ";
        e = primtest(slei);
        if (e == 1) cout << "(Primzahl) ";
        }
      }
}
// Stellt fest, ob die Faktoren richtig ermittelt wurden
void primelchen::Probe (void) //unsigned long faktoren[], unsigned long e)
{
unsigned long zahl, slei;

cout << endl << "Probe: " << endl;
cout << "Zahl der Faktoren: " << e << endl;

for ( slei = 0; slei < e; slei++)
  cout << endl << slei +1 << ". ter Faktor " << " = " << faktoren[slei] ;
cout << endl;

zahl = 1;
for ( slei = 0; slei < e; slei++)
 {
  cout << faktoren[slei] ;
  if (slei < e - 1) cout << "*";

  zahl *= faktoren[slei];
 }
cout << "=" << zahl << endl << "Zahl wurde berechnet" << endl;
}

// Ermittelt die einzelnen Faktoren einer zu testenden Zahl
unsigned long primelchen::Faktorentest(void) //unsigned long zahl, unsigned long (*faktoren)[100])
{
unsigned long slei, sleib, a, b, c, d, e;

    a = zahl;
    b = 0;
    d = 0;
    e = 0;

    for (slei= 2; slei <= ((zahl / 2) + 2); slei++)
     {
      c = primtest(slei);
      if (c == 1)
      {
       for (sleib = 2; sleib <= 25; sleib++)
        {
         b = a / slei;
         d = a % slei;
         if (d) break;
         cout << endl << "b = a / slei: " << b << " = " <<  a << "/ " << slei << "(primzahl)";
         faktoren[e++] = slei;
         a = b;
        if (b == 1) goto fertig;
        }
       }
      }
fertig: return e;
}
void primelchen::primzahlen(void)
{
 cout << endl << "Primzahlen zeigen";
 cout << endl << "Bitte kleinste Zahl eingeben: ";
 cin >> kleinste;
 cout << endl << "Bitte größte Zahl eingeben: ";
 cin >> groesste;
 cout << endl;
 for (slei = kleinste; slei <= groesste; slei++)
  {
   c = primtest(slei);
   if (c == 1) cout << " " << slei << " ";
  }
}

void primelchen::Einzelfaktoren(void)
{
 cout << endl << "Zahl auf Faktoren prüfen";
 cout << endl << "Bitte eine Zahl eingeben: ";
 cin >> zahl;
 c = primtest(zahl);
 if(c == 1)
  cout << endl << " Zahl ist selber Primzahl: " << c;
  else
   {
    cout << endl << "Weiter mit berechnen" << endl;
    teilbarkeit(zahl);
    e =  Faktorentest();
    Probe();
   }
}

Gecoded wurde auf SUSE LEAP 42.1 mit codeblocks 13.12 und gcc

Besser du gliederst einige Passagen aus und machst Funktionen draus.
So kannst du den Fehler leichter eingrenzen. Fürs obere Beispiel kannste
ja mal auf C umschreiben. Oder faulheitshalber gleich so compilieren.
Habs mir mal bei der Umschulung geschrieben.
Wir sollten als "Hausaufgabe" Zahlen in ihre Primfaktoren zerlegen.
War dazu viel zu faul und hab lieber gecodet.
Das du nix kriegst ist kein Wunder, haste ja nur unten ausserhalb der
Schleifen deine printf-Anweisung.
**
Vive la paresse!!!
**

SeppJ

rustyoldguy schrieb:

Ist zwar C++ und mit goto aber die Funktionen kannste vielleicht
was brauchen von.

Das ist schrecklicher Code! Wieso stellst du den hier als Hilfe ein, wenn dir das selber bereits bewusst ist? Das hilft nicht, das verleitet den Threadersteller bloß dazu, diesen schrecklichen Code zu nehmen. Oder wenn es ganz schlimm kommt: Davon zu lernen.

Du könntest lieber selber eine Frage stellen, was man an deinem Programm besser machen könnte. Manches scheint dir schon selber bewusst zu sein. Aber auch das Design deiner Funktionen und die Wahl deiner Algorithmen sind schrecklich. Eine detaillierte Analyse wäre jedoch ziemlich aufwendig, das mache ich nur, falls du daran überhaupt interessiert bist.

Ich denke, davon wird keiner lernen können.
Bei der Struktur und dem Einrückungstil steigt da keiner, auch der Autor nicht, richtig durch.

Sonst hätte er die Erfahrung aus den letzten 20 Jahren da mal rüberblicken lassen.