if(a[i]) funktioniert nicht

[nfet (Gast)]

Wieso funktioniert

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

#define N 1000000

int main()
{
    int a[N];
    int i = 0;
    int j = 0;
    int z = 0;

    a[1]=0;
    for(i=2; i<= N; i++ )
        a[i] = 1;

    for( i=2; i<=N/2; i++ )
    {
        //if (a[i])
        {
            z = i+i;
            for( j=z; j<=N; j = j + i )
            {
                 a[j] = 0;
            }
        }

    }
    return 0;
}

aber wenn man

if (a[i])

 wieder mit herein nimmt nicht mehr (zumindest auf meinem PC und mit 
diesem N)?

[Thomas (Gast)]

Welcher (angenommene) Fehler tritt auf? Kommt ein Kuckuck aus dem PC und 
kräht "Es funktioniert nicht"?

[B. S. (bestucki)]

nfet schrieb:
> for(i=2; i<= N; i++ )
>         a[i] = 1;

Hier fängt das Problem schon an. Wenn i == N ist, greifst du unerlaubt 
auf Speicher zu, der sich hinter dem Array befindet.

nfet schrieb:
> aber wenn manif (a[i]) wieder mit herein nimmt nicht mehr (zumindest auf
> meinem PC und mit
> diesem N)?

Was geht nicht? Wie äussert sich das?

[nfet (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

[Daniel A. (daniel-a)]

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.

[Samuel J. (capstrovor)]

1. Solltest du in
> for(i=2; i<= N; i++ )
>         a[i] = 1;

i < N verwenden

und 2.

> if(a[i])
welche Bedingung? Wenn a[i] was ist?
Schreib die if-Bedingung ausführlicher.
Was sollte das Programm eigentlich machen?

[nfet (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).

[Yalu X. (yalu) (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:

  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

    for( i=2; i*i<N; i++ )

was die Sache sehr viel schneller macht.

[B. S. (bestucki)]

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.

[Johann L. (gjlayde)]

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.

Muss doch kleinergleich √N sein, oder?  Sonst wird z.B. bei N=9 nicht 
mit 3 gesiebt.

be stucki schrieb:
> Gerade Zahlen kann man auch gleich weglassen.

Nur gerade Zahlen != 2.

[Yalu X. (yalu) (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:

    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:

            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.