if(a[i]) funktioniert nicht

Gast #3669078
Wieso funktioniert
1
#include <stdio.h>
2
#include <stdlib.h>
3

4
#define N 1000000
5

6
int main()
7
{
8
    int a[N];
9
    int i = 0;
10
    int j = 0;
11
    int z = 0;
12

13
    a[1]=0;
14
    for(i=2; i<= N; i++ )
15
        a[i] = 1;
16

17
    for( i=2; i<=N/2; i++ )
18
    {
19
        //if (a[i])
20
        {
21
            z = i+i;
22
            for( j=z; j<=N; j = j + i )
23
            {
24
                 a[j] = 0;
25
            }
26
        }
27

28
    }
29
    return 0;
30
}

aber wenn man
1
if (a[i])
 wieder mit herein nimmt nicht mehr (zumindest auf meinem PC und mit 
diesem N)?
Gast
:D
Ja so ähnlich ist es.

Es kommt das berühmte .exe funktioniert nicht mehr Windows kann online 
nach einer Lösung für das Problem suchen.
Problemsignatur:
  Problemereignisname:  APPCRASH
  Ausnahmecode:  c00000fd
  Ausnahmeoffset:  00001b43
nfet schrieb:
>     int a[N];
>     a[1]=0;
>     for(i=2; i<= N; i++ )
>         a[i] = 1;

Das erste element ist element 0, nicht 1. Das letzte ist somit N-1. Bei 
a[i] mit n für i, hasst du einen bufferoverflow. Danach kann ALLES 
passieren. WENN windows das merkt hast du glück, deshalb der absturz. 
Bei diesem scheinbar sinfreien programm musst du u.a. das <= durch < 
ersetzen und 2 durch 1 und 1 durch 0.
Gast
Dieses Programm findet Primzahlen, aber eigentlich recht egal was es 
macht. Das mit dem Overflow stimmt, hätte da aber nicht schon früher ein 
Fehler kommen müssen?
Und kann man das nicht mit einem int a[N+1]; beheben?
if (a[i]) könnte man auch als if (!(a[i] == 0)) schreiben oder in diesem 
Fall auch als if (a[i] == 1).
Moderator
nfet schrieb:
> Das mit dem Overflow stimmt, hätte da aber nicht schon früher ein
> Fehler kommen müssen?

Nicht jeder Array-Overrun führt automatisch zu einem
Speicherzugriffsfehler. Liegt das Array nicht ganz am Ende des
prozesseigenenen Speicherbereichs, kann das Programm ungestraft auch
noch ein Stück über das Array-Ende hinaus schreiben oder lesen.

> Und kann man das nicht mit einem int a[N+1]; beheben?

Ja.

> if (a[i]) könnte man auch als if (!(a[i] == 0)) schreiben oder in diesem
> Fall auch als if (a[i] == 1).

Da die Array-Elemente sowieso nur zwei unterschiedliche Werte annehmen
können, kannst du es auch als bool deklarieren (dazu stdbool.h
includen). Gibst zu dem Array a dann noch einen treffenden Namen (z.B.
prime, isPrime o.ä.), passt auch die If-Abfrage ohne expliziten
Vergleich:
1
  if(prime[i]) { ... }

Übrigens müssen beim Sieb des Eratosthenes für i nur Zahlen kleiner √N
berücksichtigt werden, um alle Primzahlen bis N zu ermitteln. Der äußere
Schleifenkopf kann damit auch so aussehen
1
    for( i=2; i*i<N; i++ )

was die Sache sehr viel schneller macht.
nfet schrieb:
> if (a[i]) könnte man auch als if (!(a[i] == 0)) schreiben oder in diesem
> Fall auch als if (a[i] == 1).

Oder auch if(a[i] != 0). Deine Lösung reicht aber und wird von jedem, 
der in seinem Leben länger als 5min C programmiert hat, auch verstanden.

Yalu X. schrieb:
> Übrigens müssen beim Sieb des Eratosthenes für i nur Zahlen kleiner √N
> berücksichtigt werden, um alle Primzahlen bis N zu ermitteln. Der äußere
> Schleifenkopf kann damit auch so aussehen
>     for( i=2; i*i<N; i++ )
>
> was die Sache sehr viel schneller macht.

Gerade Zahlen kann man auch gleich weglassen.
Moderator
Johann L. schrieb:
> Muss doch kleinergleich √N sein, oder?  Sonst wird z.B. bei N=9 nicht
> mit 3 gesiebt.

Ja, richtig.

Die besagte Zeile muss also korrekt lauten:
1
    for( i=2; i*i<=N; i++ )

Dafür kann man die innere Schleife auch noch etwas optimieren, indem man
j nicht bei 2*i, sondern erst bei i*i loslaufen lässt:
1
            for( j=i*i; j<=N; j = j + i )

Wen die Multiplikation in i*i noch stört, kann diese Quadratzahlen auch
durch fortgesetztes Aufaddieren ungerader Zahlen in der äußeren Schleife
gewinnen.

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 12 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.