Primzahlen Sieb

[harryi]

Hallo,

ich programmiere zurzeit als Anfänger einen Primzahlen Sieb nach eratosthenes Methode.

Ich habe eigentlich alles verstanden, aber irgendwie will es nicht klappen.
Könnt ihr mir sagen, wo der Fehler liegt?
Wie kann ich die Lösung mit stringgrid1 verknüpfen?

Danke

Delphi-Quellcode:

procedure TForm1.eratosthenes;
var prim:Array[1..100000]of Integer;           //Zahlen von 1 bis 250000
    i,v:integer;                               //i=Zahl

begin
prim[i]:=1;
stringgrid1.cells[0,1]:='0';
for i:=1 to nmax do
    begin
    v:=2;
    while v*i<=nmax do
    begin
    prim[i]:=0;
    v:=v+1;
    end
    end
end;

[Noedel]

so wie ich das sehe, gibst du nichts aus, rechnest nur...

[schöni]

Zitat:

Zitat von harryi

Delphi-Quellcode:

procedure TForm1.eratosthenes;
var prim:Array[1..100000]of Integer;           //Zahlen von 1 bis 250000
    i,v:integer;                               //i=Zahl

begin
prim[i]:=1;
stringgrid1.cells[0,1]:='0';
for i:=1 to nmax do
    begin
    v:=2;
    while v*i<=nmax do
    begin
    prim[i]:=0; //prim[i] ist gleich 0 statt v
    v:=v+1;
    end
    end
end;

Dem Array prim wird immer der Wert 0 zugewiesen. Weise den Wert v zu!

Ich habe jetzt den Primzahlalgo nicht im Kopf, weiß aber, das eine Primzahl nur durch 1 und durch sich selber ohne Rest teilbar ist. Daraus sollte sich ein Algo bauen lassen. Egal wie schnell der dann erst mal ist.

[Mikescher]

Und wenn du mal eine schnelle Möglichkeit brauchst (wirst du bei 250000 Zahlen wohl brauchen) könntest du den Sieb des Eratosthenes benutzen :zwinker:

Ich hab den au mal geschrieben und als Beispiel grad mal angehängt

MfG Mikescher

[harryi]

Dankeschön, Prinzip sollte auch die von erastotenes werden^^

ich wende mich an euch, falls ich noch fragen habe,

[harryi]

Ich kriege das mit der Input immer noch nicht hin.

Also mein Ziel ist es bei Spalte 1 die Nummerierung zu haben, Index vom Primzahl und dann rechts in der Spalte 2 dann meine Primzahl.

Delphi-Quellcode:

procedure TForm1.eratosthenes;
var prim:Array[1..100000]of Integer;           //Zahlen von 1 bis 100000
    i,v,nmax:integer;                          //i=Zahl
begin
nmax:=spinedit1.value;
for i:=2 to nmax do
    prim[i]:=1;
    v:=2;
    while v*i<=nmax do
    begin
    prim[i]:=0;
    v:=v+1;
    end;


for i:=1 to nmax do
  if prim[i]=1 then

Bei mir ist wenn prim[i]=1 eine Primzahl , alle die durch das v(Vielfachen) teilbar ist, werden nicht aufgelistet also prim[i]:=0.

Hilfe

[Blup]

Zitat:

Zitat von harryi

Ich habe eigentlich alles verstanden, aber irgendwie will es nicht klappen.

Du hast vieleicht alles verstanden, aber nicht richtig umgesetzt.
Rück deinen Code mal ordentlich ein, dann siehst du vieleicht auch schon den ersten Fehler.

Delphi-Quellcode:

for i:=2 to nmax do 
  prim[i]:=1;

Das Array wird ordentlich initialisiert, so weit so gut.

Fehler:

Delphi-Quellcode:

while v*i<=nmax do
begin

Die Variable i ist nach dem Schleifendurchlauf undefiniert, das müsste dir der Compiler an dieser Stelle auch melden.
Tatsächlich wird hier eine neue Schleife benötigt, in der für jede Zahl die eine Primzahl ist, das "Aussieben" erfolgt.

Richtig:

Delphi-Quellcode:

for i:=2 to nmax do
begin
  if prim[i] = 1 then
  begin
    v:=2;
    while v*i<=nmax do
    begin

Fehler:

Delphi-Quellcode:

prim[i]:=0;

Natürlich nicht i sondern v * i, das jeweilige vielfache der Primzahl ist keine Primzahl.

Richtig:

Delphi-Quellcode:

prim[v * i]:=0;