Решето́ А́ткина — алгоритм нахождения всех простых чисел до заданного целого числа N. Алгоритм был создан А. О. Л. Аткином и Д. Ю. Бернштайном [1][2]. Заявленная авторами асимптотическая скорость работы алгоритма соответствует скорости лучших ранее известных алгоритмов просеивания, но в сравнении с ними решето Аткина требует меньше памяти.
Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде ax²+by²). Предыдущие алгоритмы в основном представляли собой различные модификации решета Эратосфена, где использовалось представление чисел в виде редуцированных форм (как правило — в виде произведения xy).
В упрощённом виде алгоритм может быть представлен следующим образом:
Для уменьшения требований к памяти «просеивание» производится порциями (сегментами, блоками), размер которых составляет примерно .
Для ускорения работы алгоритм игнорирует все числа, которые кратны одному из нескольких первых простых чисел (2, 3, 5, 7, …). Это делается путём использования стандартных структур данных и алгоритмов их обработки, предложенных ранее Полом Притчардом (англ. Pritchard, Paul)[3]. Они известны под названием англ. wheel sieving. Количество первых простых чисел выбирается в зависимости от заданного числа N. Теоретически предлагается брать первые простые примерно до . Это позволяет улучшить асимптотическую оценку скорости алгоритма на множитель . При этом требуется дополнительная память, которая с ростом N ограничена как . Увеличение требований к памяти оценивается как .
Версия, представленная на сайте одного из авторов[4], оптимизирована для поиска всех простых чисел до миллиарда ( ), в ней исключаются из вычислений числа, кратные двум, трём, пяти и семи (2 × 3 × 5 × 7 = 210).
По оценке авторов[2] алгоритм имеет асимптотическую сложность и требует бит памяти. Ранее были известны алгоритмы столь же асимптотически быстрые, но требующие существенно больше памяти[5][6]. Теоретически в данном алгоритме сочетается максимальная скорость работы при наименьших требованиях к памяти. Реализация алгоритма, выполненная одним из авторов, показывает достаточно высокую практическую скорость[4].
В алгоритме используется два вида оптимизации, которые существенно повышают его эффективность (по сравнению с упрощённой версией).
Ниже представлена реализация упрощённой версии на языке программирования C, иллюстрирующая основную идею алгоритма — использование квадратичных форм:
int limit = 1000;
int sqr_lim;
bool is_prime[1001];
int x2, y2;
int i, j;
int n;
// Инициализация решета
sqr_lim = (int)sqrt((long double)limit);
for (i = 0; i <= limit; i++) is_prime[i] = false;
is_prime[2] = true;
is_prime[3] = true;
// Предположительно простые — это целые с нечётным числом
// представлений в данных квадратных формах.
// x2 и y2 — это квадраты i и j (оптимизация).
x2 = 0;
for (i = 1; i <= sqr_lim; i++) {
x2 += 2 * i - 1;
y2 = 0;
for (j = 1; j <= sqr_lim; j++) {
y2 += 2 * j - 1;
n = 4 * x2 + y2;
if ((n <= limit) && (n % 12 == 1 || n % 12 == 5))
is_prime[n] = !is_prime[n];
// n = 3 * x2 + y2;
n -= x2; // Оптимизация
if ((n <= limit) && (n % 12 == 7))
is_prime[n] = !is_prime[n];
// n = 3 * x2 - y2;
n -= 2 * y2; // Оптимизация
if ((i > j) && (n <= limit) && (n % 12 == 11))
is_prime[n] = !is_prime[n];
}
}
// Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)].
// (основной этап не может их отсеять)
for (i = 5; i <= sqr_lim; i++) {
if (is_prime[i]) {
n = i * i;
for (j = n; j <= limit; j += n) {
is_prime[j] = false;
}
}
}
// Вывод списка простых чисел в консоль.
printf("2, 3, 5");
for (i = 6; i <= limit; i++) { // добавлена проверка делимости на 3 и 5. В оригинальной версии алгоритма потребности в ней нет.
if ((is_prime[i]) && (i % 3 != 0) && (i % 5 != 0)){
printf(", %d", i);
}
}
program atkin;
var is_prime:array[1..10001] of boolean; jj:int64;
procedure dosieve(limit:int64);
var i,k,x,y:int64; n:int64;
begin
for i:=5 to limit do
is_prime[i]:=false;
for x:=1 to trunc(sqrt(limit)) do
for y:=1 to trunc(sqrt(limit)) do
begin
n:=4*sqr(x)+sqr(y);
if (n<=limit) and ((n mod 12 = 1) or (n mod 12 = 5)) then
is_prime[n]:=not is_prime[n];
n:=n-sqr(x);
if (n<=limit) and (n mod 12 = 7) then
is_prime[n]:=not is_prime[n];
n:=n-2*sqr(y);
if (x>y) and (n<=limit) and (n mod 12 = 11) then
is_prime[n]:=not is_prime[n];
end;
for i:=5 to trunc(sqrt(limit)) do
begin
if is_prime[i] then
begin
k:=sqr(i);
n:=k;
while n<=limit do
begin
is_prime[n]:=false;
n:=n+k;
end;
end;
end;
is_prime[2]:=true;
is_prime[3]:=true;
end;
begin
dosieve(10000);
for jj:=1 to 10000 do
if is_prime[jj] then
writeln(jj);
end.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .