Реализации алгоритмов/Решето Аткина: различия между версиями
Содержимое удалено Содержимое добавлено
Добавлены ссылки на Решето Сундарама и Эратосфена |
Оптимизация кода |
||
Строка 19:
* Флаги «простое\составное» хранятся упакованными в массив битов (<code>vector<bool></code> для С++, <code>BitSet</code> для Java и т. п.). Значение ''n''-го бита ''true'' соответствует простому ''n'', ''false'' — составному.
* Умножение на степень двойки производится операцией побитового сдвига (''<<''). Например <code>a << 2</code> вместо <code>4 * a</code>.
* Для уменьшения риска переполнения вычисления ведутся в типе длинное целое (<code>unsigned long long</code> в C++, <code>long</code> в Java); на выходе значения выдаются в заданном целочисленном типе.
* Квадраты последовательных натуральных чисел вычисляются по формуле ''(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''.
Строка 26 ⟶ 27 :
<source lang="cpp">
//
#include <vector>
namespace
▲ template < typename T, typename Sequence >
▲ void sieve (T const limit, Sequence &primes) {
// Очистка результирующей последовательности
primes.clear();
// Числа 2 и 3 — заведомо простые
if (limit >
primes.push_back(
else
return;
if (limit >
primes.push_back(
else
return;
// Предварительное просеивание
for (
for (
// n = 4x² + y²
n = (x2 <<
if (n <= limit && (n %
sieve[n].flip();
// n = 3x² + y²
n -= x2;
if (n <= limit && n %
sieve[n].flip();
// n = 3x² - y² (при x > y)
if (x2 > y2) {
n -= y2 <<
if (n <= limit && n %
sieve[n].flip();
}
}
// Все числа, кратные квадратам, помечаются как составные
for (
if (sieve[r])
for (n = r2; n < limit; n += r2)
sieve[n] = false;
// Занесение чисел в результирующую последовательность
for (n =
if (sieve[n])
primes.push_back(n);
}
}</source>▼
▲</source>
Пример использования:
<source lang="cpp">
Строка 86 ⟶ 83 :
#include <vector>
#include "
Строка 93 ⟶ 90 :
int main () {
Sequence primes;
// Вывод последовательности
for (Sequence::const_iterator iterator = primes.begin(); iterator != primes.end(); ++iterator)
Строка 104 ⟶ 101 :
Простые числа вычисляются для типа <code>int</code>. Результирующая последовательность должна иметь тип, реализующий интерфейс <code>List<Integer></code> (например, <code>ArrayList<Integer></code>).
<source lang="java">
//
import java.util.BitSet;
import java.util.List;
public class
public static void
// Очистка результирующей последовательности
primes.clear();
Строка 123 ⟶ 120 :
return;
// Предварительное просеивание
BitSet sieve = new BitSet();
for (
for (
// n = 4x² + y²
n = (x2 <<
if (n <= limit && (n %
sieve.flip((int)n);
// n = 3x² + y²
n -= x2;
if (n <= limit && n %
sieve.flip((int)n);
// n = 3x² - y² (при x > y)
if (x2 > y2) {
n -= y2 <<
if (n <= limit && n %
sieve.flip((int)n);
}
}
// Все числа, кратные квадратам, помечаются как составные
for (
if (sieve.get(r))
for (n = r2; n < limit; n += r2)
sieve.set((int)n, false);
// Занесение чисел в результирующую последовательность
for (
if (sieve.get(
primes.add(
}
}
Строка 163 ⟶ 160 :
public static void main (String []args){
ArrayList<Integer> primes = new ArrayList<>();
// Вывод последовательности
for (int prime : primes)
|