Преглед на кода на Решето на Аткин

{{без източници|}}


'''Решето на Аткин''' е метод за намиране на всички [[Просто число|прости числа]], които не надвишават дадена естествения ''лимит''. За разлика от [[Решето_на_Ератостен|Решето на Ератостен]], което последователно елиминира числа, кратни на вече намерени прости числа, този [[алгоритъм]] извършва предварително пресяване и след това елиминира от намерените числа кратни на прости числа на квадрат, поради което той има теоретично по-добър индикатор за асимптотична сложност <math>\mathop O(\frac{1}{\log \log (limit)})</math>.

'''Автори:''' Артър Оливър Лонсдейл Аткин, Даниел Джулиъс Бърнстейн (''Английски'' Arthur Oliver Lonsdale Atkin, Daniel Julius Bernstein).

=Алгоритъм=
# Числата 2, 3 и 5 са очевидно прости.
# Създава се “решето” - списък, който свързва всяко естествено число ''n'' от диапазона (5; ''лимит''] с флаг "прост\съставен". Първоначално всички флагове са зададени на " съставна” позиция.
# За следващото ''n'' от диапазона (5; ''limit''] се намира остатъкът от деленето на 60:
#* 1, 13, 17, 29, 37, 41, 49, 53: уравнение - ''4x² + y² = n''; (1)
#* 7, 19, 31, 43: уравнение - ''3x² + y² = n''; (2)
#* 11, 23, 47, 59: уравнение - ''3x² − y² = n'' (за ''x > y'') (3)
# Остатъчна стойност, която не е равна на никоя от горните, показва, че ''n'' е съставно число и следователно се изключва от по-нататъшно разглеждане. В противен случай, ако съответното уравнение има нечетен брой решения (двойки естествени стойности ''x'' и ''y''), ''n'' се отбелязва в "решето" като "просто".
# Процедурата се повтаря, започвайки от стъпка 3, докато бъдат претърсени всички ''n ≤ limit''.
# Накрая, за всяко намерено просто число ''n'', всички кратни на неговия квадрат се маркират в "решето" като "съставно".

=Реализации=
Реализациите по-долу предприемат следните стъпки за оптимизиране на изчисленията:
* Simple\composite флаговете се съхраняват пакетирани в масив от битове (<code>vector<bool></code> за C++, <code>BitArray</code> за C#, <code>BitSet</code> за Java, <code>BitVec</code> за Rust и др.), върнат от функцията. Стойността на ''n''-тия бит ''true'' съответства на просто ''n'', ''false'' на съставно.
* Умножението на степен две се извършва с помощта на операция за побитово преместване (''<<''). Например <code>a << 2</code> вместо <code>4 * a</code>.
* За да се избегне препълване, изчисленията се извършват в тип дълго цяло число; стойностите се въвеждат в „ситото“ в тип редовно цяло число (<code>unsigned long long</code> / <code>unsigned</code> в C++, <code>long</code> / <code>int</code> в C# и Java, <code>u64</code> / <code>u32</code> в Rust).
* Квадратите на последователните [[Естествено число|естествени числа]] се изчисляват по формулата ''(x + 1)² = x² + 2x + 1'', т.е. чрез събиране на последователни нечетни числа. С други думи, ако ''квадрати'' е поредица от квадрати на естествени числа ''{0² = 0, 1² = 1, 2² = 4...}'', а ''коефициенти'' е поредица от нечетни числа ''{1, 3, 5...}'', след това ''квадрат<sub>i+1</sub> = квадрат<sub>i</sub> + шансове<sub>i</sub> '' (за всеки ''i ≥ 0 '').
* ''n'' се дели с остатък на 12 (не на 60). Получените стойности 1 и 5 съответстват на случай (1), 7 - (2), 11 - (3), други - съставни ''n''.

[[Категория:Криптографски алгоритми]]