Primzahlsuche in C++ (optimierbar?)

[MudGuard]

Hi,

danke!
bei einem versuch mit dem bereich 1-10.000.000 wurde das script um 10 sekunden schneller.
allerdings habe ich ceil anstatt von floor verwendet; ist das nicht (in diesem Fall) besser?

(im folgenden gehe ich davon aus, daß i positiv ist ...)

Sei s = sqrt(i) (also Quadratwurzel von i)
Sei f = floor(s) und c = ceil(s)

Jetzt gilt: f <= s <= c.

Ist s eine Ganzzahl, ist f = s = c, es ist also egal, ob f oder c benutzt wird.

Ist s keine Ganzzahl, ist f kleiner als s und c größer als s, und c = f + 1.
Es gilt also: f < s < c bzw. f² < s² < c² bzw. f² < i < c²
c² ist bereits größer als i, also ist auch c*x > i für x >= c.
Damit c*x = i sein könnte (also Teilbarkeit existiert), muß x also kleiner als c sein.
(mit anderen Worten: es muß einen Teiler geben, der kleiner als c ist).

Das größtmögliche x, welches kleiner als c ist, ist f.
Also reicht es vollkommen, bis (einschließlich) f zu probieren, also bis floor(sqrt(i)).

cu,
Andreas