Недавно заинтересовался алгоритмами вычисления простых чисел: Для больших чисел 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.`
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021