Оптимальный алгоритм проверки числа на простоту?!


#1

Недавно заинтересовался алгоритмами вычисления простых чисел: Для больших чисел x стандартный алгоритм проверки всех делителей от 2 до √x работает довольно долго, поэтому возникает естественная идея улучшить алгоритм и проверять только простые делители от 2 до √x. Моя реализация данной идеи представляет собой “говнокод”, написанный в условии отсутствия знаний о корреляции времени работы кода и его структурой, поэтому обращаюсь к опытным программистам с вопросом: Возможно ли написать этот “улучшенный” алгоритм так, чтобы он работал быстрее стандартного?

P.S. Стандартный алгоритм: var flag: boolean; for var i := 2 to 1000000 do begin flag := true; for var j := 2 to trunc(sqrt(i)) do if i mod j = 0 then begin flag := false; break end; if flag then print(i); end;

Моя реализация “улучшенного” алгоритма: `function SequenceOfSimple(x: BigInteger): sequence of BigInteger; begin if x <= 1 then begin print(‘Некорректный ввод: запрос последовательности простых, меньших 1’); halt; end else begin var pre_result := new System.Collections.ArrayList; pre_result.Add(2); var i:BigInteger := 3; var flag: boolean; while i <= x do begin flag := true; foreach var j in pre_result do if i mod j.ToString.ToInteger = 0 then begin flag := false; break end; // print(‘break norm’); if flag then pre_result.Add(i); i += 1; end; result := seqgen(pre_result.Count-1,i -> pre_result[i].ToString.ToBigInteger); // print(pre_result); end; end;

begin foreach var i in SequenceOfSimple(power(10,6).TruncBigInteger) do print(i); end.`


#2

Код на этом форуме выделяется так:

```
код
```

Отредактируйте для начала своё первое сообщение.


#3

Не понял, для чего выбран тип BigInteger? Вы собираетесь методом i += 1 дойти до чисел, превышающих 10^19 ?

new System.Collections.ArrayList; - лучше new List< BigInteger >;

i mod j.ToString.ToInteger = 0 - это что такое было? Почему не просто i mod j = 0 ?

А прочее - да, нормально свой код сначала отформатируйте.

P.S. result := seqgen(pre_result.Count - 1, i -> pre_result[i].ToString.ToBigInteger); - это повод для отдельного разговора))