Hi, ich muß immer wieder Zahlen n auf ihre modulo-Reste testen, diese Schleife wird sehr häufig durchlaufen:
Delphi-Quellcode:
n := ...
r := n mod 17;
if r = 1 then
begin
...
end
else
if r = 4 then
begin
...
end;
Von allgemeinerem Interesse ist das Problem vielleicht bei Primzahl-Sieben.
Mein Eratosthenes-Sieb braucht auf meiner alten Gurke für Primzahlen < 10^9 ca 40s.
Da ich Primeln bis 10^12 brauche, bin ich auf Atkin (siehe wiki) umgestiegen. Dort fallen viele Rechnungen modulo 12 an. z.B.:
Delphi-Quellcode:
n := ...
r := n mod 12;
if (r = 1) or (r = 5) then
Sieve.Bits[n] := not Sieve.Bits[n];
Durch die ganzen modulos läuft Atkin bei mir noch langsamer als Eratosthenes, was eigentlich nicht sein sollte.
Da gibts doch bestimmt irgendwelche Tricks?!