4. Problem bei Speicheranforderung für Array

Problem bei Speicheranforderung für Array

  • E

    Hi,

    bin neu hier 🙂

    Hab ein Problem mit der Speicheranforderung - zumindest glaub ich das^^

    Ich habe einen nen Code geschrieben um das sieb des eratosthenes umzusetzen.

    /*______________Sieb des Eratosthenes_____________________

Feld von N Elementen beginnend von 2!

*/
#include <stdio.h>
#include <stdlib.h>

#define N          100000                                                       /*Anzahl*/ // zum testen eine Zahl einsetzen
#define markiert   1                                                            //Statusinformation für markierte Zahlen
#define unmarkiert 0                                                            //Statusinformation für unmarkierte Zahlen

struct Feld                                                                     //Struktur mit 2 Informationen - Zahl und Status
{
       int Zahl;
       int Status;
};

int main(void)
{
                                                                                //Feld mit N Zahlen mit jeweils einer Statusinfo
    struct Feld *feld = 0;
    feld = new Feld[N];
                                                                                //Feld füllen beginnend mit 2

    for(int i = 0; i < N-1; i++) 
    { 
        feld[i].Zahl = i+2;
        feld[i].Status = unmarkiert;
        printf("Zahl: %d Status: %d \n",feld[i].Zahl,feld[i].Status);

    }

    int u;                                                                      //variable für kleinste unmarkierte Zahl
	int x;                                                                      //provisorische variable zur änderung von i
    int counter = 0;                                                            //counter für Feldinhalt
    int AnzMarkierungen=0; 
    int AnzPrimzahlen=0;

    while(counter < N-1)
    {
                                                                                //bestimme kleinste unmarkierte Zahl -> u
        if (feld[counter].Status == unmarkiert) 
        {
           u = feld[counter].Zahl;
           printf("Primzahl: %d \n", u);                                      //u = Primzahl
           if (u*u <= N)                                                        //wenn u² > N ergeben alle unmarkierten Zahlen Primzahlen!
           {
              for(int i = u*u; i<=N; i = x)
              { 
                  feld[i-2].Status = markiert;
                  AnzMarkierungen++;
                  printf("Markiere: %d \n", feld[i-2].Zahl);
                  if(i+u <= N) x=i+u;
                  else x= N+1;
              }
           }         
           AnzPrimzahlen++;                  
        }

        counter++;
    } 
   printf("Anzahl Markierungen: %d Anzahl Primzahlen: %d \n",AnzMarkierungen,AnzPrimzahlen);
   delete[] feld;
   feld = 0;
   system("PAUSE");                                                                           

return 1;  
};

    Das Problem dabei ist, dass das Programm nach der Primzahl 46349 abstürzt.
    Debugging zeigt an dass das Programm auf unbefugten Speicher schreiben will.

    Jemand eine idee was da falsch läuft?
    Wäre echt nett, danke schonmal

    mfg Energizer

    0
  • C

    Ohne die Sache genauer betrachtet zu haben: Gehe ich recht in der Annahme, daß Du auf einer 32-Bit-Maschine unterwegs bist? Dann läuft dir nämlich bei 46341² dein int über. Und da dürfte deine Baustelle liegen.

    0
  • Mod

    Du hast in deinem Code zwei Zeilen C++ und die würde man in C++ niemals so benutzen. Zeilen 27 und 68. Nutze in C malloc und free. In C++ machst du hingegen alles ganz anders. Ich verschiebe dich mal ins C-Forum.

    Zu verschiedenen Implementierungen des Primzahlsiebes siehe beispielsweise diesen aktuellen Thread:
    http://www.c-plusplus.net/forum/p2321674#2321674

    0
  • C

    Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum C (C89, C99 und C11) verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • E

    Caligulaminus schrieb:

    Ohne die Sache genauer betrachtet zu haben: Gehe ich recht in der Annahme, daß Du auf einer 32-Bit-Maschine unterwegs bist? Dann läuft dir nämlich bei 46341² dein int über. Und da dürfte deine Baustelle liegen.

    Damit hast recht aber mein pc meint er hätte 64 bit^^
    ->
    ich verwende jtz "unsigned int" damit komm ich schonmal stück weiter
    -> funzt auf jedenfall schonmal bis 10^6 aber irgendwo verschwinden primzahlen^^ es fehlen 5 Primzahlen(für n = 10^6) oder 3(für n = 500.000)

    0
  • N

    Wäre an dieser Stelle als Datentyp für N nicht size_t angebrachter?

    Entsprechend:

    size_t N = 100000
    0
  • E

    auch ne möglichkeit -

    mein letztes problem is das ich falsche Primzahlenanzahlen herausbekomme wenn ich in zeile 51:

    if (u*u <= N)

    verwende - jedoch mit

    if(sqrt(N) >= u)

    richtige.

    ->Was auch das problem mit int und size_t bzw unsigned int beheben würde ^^

    Jemand dafür noch ne idee danach kann man das hier schließen.

    0
  • Mod

    u*u sieht ebenfalls nach einem Ausdruck aus, der gerne mal überlaufen kann.

    Mir ist rätselhaft, wozu die Abfrage überhaupt da sein soll. Überhaupt ist einiges umständlich, einen Link zu wesentlich einfacheren Lösungen hast du schon bekommen.

    0
  • E

    Wenn das quadrat von u größer als N ist dann sind alle unmmarkierten zahlen primzahlen.

    Das es noch bissle umständlich is weis ich selbst- mir gehts eigentlich grad nur drum das es funktioniert.
    Und da unser Datenstruckturen Prof. meint wir dürfen keine bibliotheken einbinden - kann ich die sqrt(N) lösung nicht verwenden!(die bisher eingebundenen sind nur zum testen drin)

    0
Anmelden zum Antworten