Sieb des Eratosthenes

[Foxgrove]

Hallo,

eigentlich ist es ganz einfach a b e r im Detail
schlage ich mich seit 2 Tagen damit herum: :wall: :wall:

Ein ganz bekanntes Programm in VBASIC ermittelt alle Primzahlen bis zu einem
eingegebenen Wert über 2 gleiche / parallele Listen (Vektoren, Feldvariable)
Man nennt es "Das Sieb des Eratosthenes".

Die erste Liste übernimmt alle Zahlen bis zum gesuchten Wert
Die andere Liste genausoviele Elemente, wird mit NULLEN aufgefüllt.

Dann geht eine Schleife (die äußere) von 2 bis Quadratwurzel aus dem Endwert ( also 7 wenn Primzahlen bis 50 gesucht würden!)
Die innere Schleife beginnt/wandert mit dem Kontrollwert der äußeren Schleife und geht durch bis zum Endwert a b e r in Schrittweite äußere Schleife
Wenn die Zahl im Zahlenvektor ohne Rest teilbar ist, dann ist es keine Primzahl und im 0-er Vektor wir dann die 0 auf 1 gesetzt.

Auswertung: 1 2 3 sind immer Primzahlen und man beginnt eine 3. Schleife bei 3.
Wenn im 0-er Vektor noch eine 0 ist (überlebt hat), dann ist dies eine Primzahl.


Der CODE, entschuldigt es es BASIC:

....

....
mBis = VAL(txtBis.Text) ....... mBis := StrToInt(BisEdit.Text);
For mI = 1 to mBis
mVek(mI) = mI Vektoren präparieren
mVak(mI) = 0
Next mI

For mI = 2 to SQR(mBis) ..... Schleife von 2 bis Wurzel aus Endwert
If mVak(mI) = 1 then EXIT FOR .. Falls die Zahl schon erkannt ist, gleich weiter ...

For mY = mI to mBis STEP mI von 2 bis 50 aber in 2-er Schritten, dann 3-er , dann 5-er, ...

if mVek(mY)/mY = INT(mVek(mY)/mY) then MOD ginge ja auch
mVak(mI) = 1 .... war teilbar, keine Primzahl
end if
Next mY
Next mI

.....
Ausgabe der Primzahlen:
1 2 3 immer
For mI = 3 to mBis
if mVak(mI) = 0 then lstBox.AddItem Str$(mI)
Next mI

.......................................

An der Schrittweite der inneren Schleife werde ich meinen Verstand noch verlieren, es g e h t nicht in Delphi
Man muss schon routiniert mit While Until Schleifen umgehen können, nehme ich an?
:wall: :wall:

Wie geht es?
Darf man VBASIC Code hier veröffentlichen?
Habe ich gegen etwas verstoßen, Etikette, Rules, Gesetze oder Standards ..

Gruß Foxgrove

[Khabarakh]

Zitat:

Zitat von Foxgrove

Man muss schon routiniert mit While Until Schleifen umgehen können, nehme ich an?

So schlimm ist es nun auch wieder nicht :stupid: .

Delphi-Quellcode:

i := Start;
while i <= Stop do
begin
  DoSomethingWith(i);

  Inc(i, Step);
end;

Zitat:

Darf man VBASIC Code hier veröffentlichen?

Nur wenn man ihn artig in [code]-Tags setzt :mrgreen: .

[marabu]

Hallo Foxgrove,

die innere Schleife ist eigentlich nicht so sehr problematisch - man darf dabei nur nicht ständig in BASIC denken. Ich habe mich bemüht möglichst nah an deiner Vorgabe dran zu bleiben, aber das zweite Array war mir dann doch zu viel des Guten.

Delphi-Quellcode:

function Sieve(iMax: integer): TIntegerDynArray;
var
  i, iStep, iRoot: integer;
begin
  iRoot := Round(Sqrt(iMax));
  SetLength(Result, iMax);
  for i := 0 to Pred(iMax) do // sieve init 
    Result[i] := Succ(i); 
  for iStep := 2 to iRoot do
    for i := 2 to iMax div iStep do
      if Result[Pred(i * iStep)] mod iStep = 0 then
        Result[Pred(i * iStep)] := 0; // mark non-prime
  iMax := 3; // first non-prime index 
  for i := Succ(iMax) to High(Result) do
    if Result[i] > 0 then
    begin
      Result[iMax] := Result[i]; // pack array
      Inc(iMax);
    end;
  SetLength(Result, iMax); // adjust size
end;

Weihnachtsgrüße vom marabu

[Foxgrove]

Nun ist es geschafft.
Problem gelöst...

Foxgrove