Реализации алгоритмов/Решето Аткина: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 19:
* Флаги «простое\составное» хранятся упакованными в массив битов (<code>vector<bool></code> для С++, <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'', т. е. прибавлением последовательных нечётных чисел. Другими словами, если ''squares'' — последовательность квадратов натуральных чисел ''{0² = 0, 1² = 1, 2² = 4…}'', а ''odds'' — последовательность нечётных чисел ''{1, 3, 5…}'', то ''square<sub>i+1</sub> = square<sub>i</sub> + odds<sub>i</sub>'' (для любого ''i ≥ 0'').
* ''n'' делится с остатком на 12 (а не на 60). Полученные значения 1 и 5 соответствуют случаю (1), 7 — (2), 11 — (3), прочие — составному ''n''.
| |||