Решето на Аткин

Решето на Аткин е метод за намиране на всички прости числа, които не надвишават дадена естествения лимит. За разлика от Решето на Ератостен, което последователно елиминира числа, кратни на вече намерени прости числа, този алгоритъм извършва предварително пресяване и след това елиминира от намерените числа кратни на прости числа на квадрат, поради което той има теоретично по-добър индикатор за асимптотична сложност $\mathop {O} ({\frac {1}{\log \log(limit)}})$.

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

Алгоритъм

1. Числата 2, 3 и 5 са очевидно прости.
2. Създава се “решето” - списък, който свързва всяко естествено число n от диапазона (5; лимит] с флаг "прост\съставен". Първоначално всички флагове са зададени на " съставна” позиция.
3. За следващото 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)
4. Остатъчна стойност, която не е равна на никоя от горните, показва, че n е съставно число и следователно се изключва от по-нататъшно разглеждане. В противен случай, ако съответното уравнение има нечетен брой решения (двойки естествени стойности x и y), n се отбелязва в "решето" като "просто".
5. Процедурата се повтаря, започвайки от стъпка 3, докато бъдат претърсени всички n ≤ limit.
6. Накрая, за всяко намерено просто число n, всички кратни на неговия квадрат се маркират в "решето" като "съставно".

Реализации

Реализациите по-долу предприемат следните стъпки за оптимизиране на изчисленията:

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