Primzahlen mit versch. Tests

[Elderan]

Hallo,
für das Sieb findest du hier grundlegende Überlegungen, aber hier werden weitere Überlegungen zur Optimierung angestellt.

Wie du am Diagramm ganz unten sehen kannst, dauert das Außlassen von z.B. 2 und 3 länger als alle Zahlen zu verwenden. Erst ab den Zahlen 2-7 bekommst du einen Geschwindigkeitsvorteil, der bei 2-13 maximal ist (zumindest dort).

 

[Indi]

@Tara:
Ja, hatte ich implementiert. Allerdings nicht mit einem speziellen Algorithmus. Das Schema wiederholt sich praktisch immer nach allen 30 Zahlen. Einmal ist es die zweitfolgende Zahl die geprüft werden soll, dann die drittfolgende Zahl oder ähnlich. Kann man sich ganz leicht für einen 30er-Block raussuchen, welche Reihenfolge man verwenden muss. Kann man dann in ein Array speichern zb.

 

[Tara]

Hi!

Diese Informatikjahr-Seite ist ja wirklich toll, nicht nur zum Thema Eratosthenes. Alles schön genau erklärt, und auch Nicht-Informatiker-kompatibel!

Nur gut daß ich sie zu Beginn meiner Überlegungen noch nicht kannte, das hätte ja jegliches Nachdenken meinerseits abgewürgt!

Mein eigenes Delphi-Programm sieht so aus:

Spoiler: Code

const
  PrimeMax = 1000000;
var
  i, j, n, HalfPrimeMax: Integer;
  Sum: Int64;
  IsComposite: TBits;
begin
  HalfPrimeMax := PrimeMax div 2;
  IsComposite := TBits.Create;
  IsComposite.Size := HalfPrimeMax+1;
  for i := 1 to Trunc(Sqrt(HalfPrimeMax)) do
    if not IsComposite.Bits[i] then
    begin
      j := i+i+1;
      n := j*j shr 1;
      while n <= HalfPrimeMax do
      begin
        IsComposite.Bits[n] := True;
        Inc(n,j)
      end;
    end;
  Sum := 2;
  for i := 1 to HalfPrimeMax do
    if not IsComposite.Bits[i] then
      Inc(Sum,2*i+1);
end;

Mit den Infos von dieser Seite versuche ich mal, was besseres draus zu machen. Danke!

@ Indi:
Das Schema ist ja wirklich überichtlich, habe es mir gerade aufgemalt.

edit: Hab noch schnell den Zugriff auf die Zahlen ergänzt, so daß es Euler10 rechnet. Primzahl 2 muß separat behandelt werden.