Evgen писал(а):но постараюсь реализовать алгоритм Iskandera
Evgen, вы это о чем? Ну, хорошо, так и быть.
Насколько я понял,
Дож предлагает выполнить то что описал в один проход.
Я предлагаю самую чуточку попроще.
Для начала вам нужно подумать, как модифицировать решето Эратосфена,
чтобы имея список простых чисел от 2 до Sqrt(B), можно было начинать
вычеркивать составные числа начиная с произвольного наперед заданного числа.
Ну и соответственно сначала с помощью обычного решета получаете список простых чисел,
затем во втором проходе применяете модифицированный алгоритм.
Вадим, чот этот PA12I удобен как штаны с ширинкой сзади.
Сначала посчитать примерную длину массива,
заполнить его каким-то сигнальным значением,
выполнить процедуру,
пройти еще раз по массиву и посчитать количество элементов,
усечь массив, если нужно.
Предлагаю более удобный вариант:
- Код: Выделить всё
type
TIntArray = array of Integer;
function PrimeSieve(UpBound: Integer): TIntArray;
var
IsPrime: array of Boolean = nil;
I, Count: Integer;
J: Int64;
begin
if UpBound < 2 then
exit(nil);
SetLength(IsPrime, UpBound + 1);
for I := 0 to High(IsPrime) do
IsPrime[I] := True;
Count := 0;
for I := 2 to High(IsPrime) do
if IsPrime[I] then
begin
Inc(Count);
J := Int64(I) * Int64(I);
while J <= UpBound do
begin
IsPrime[J] := False;
Inc(J, I);
end;
end;
SetLength(Result, Count);
J := 0;
for I := 2 to High(IsPrime) do
if IsPrime[I] then
begin
Result[J] := I;
Inc(J);
end;
end;
По скорости постараюсь вечером сравнить.
(Правда есть загвоздка со временем тут я просто заранее предсказать не могу. )