Решето Эратосфена перечисляет все простые числа до верхней границы n включительно. Здесь программы на Rust выводят 168 простых чисел, не превышающих 1000. Граница включается; 0 и 1 не являются простыми.

Шаги решета и начало с квадрата

1. Выделите место для n + 1 элементов логического типа с индексами от 0 до n. Базовая версия инициализирует их истиной, затем отмечает 0 и 1 как ложь. При границе меньше 2 возвращается пустой результат до обращения к индексу 1.
2. Проверяйте кандидатов p по возрастанию, начиная с 2. Если отметка ещё истинна, p — простое число: отмечайте его кратные как ложные начиная с \(p^2\) с шагом p. Само число p не вычёркивайте.
3. Вычёркивать кратные достаточно для кандидатов с \(p^2\le n\), потому что у каждого составного числа есть простой множитель, не превосходящий его квадратного корня.
4. В конце просмотрите числа от 2 до n и выведите все числа с оставшейся истинной отметкой. Диапазон вывода не ограничивается квадратным корнем.

Кратное \(kp\), меньшее \(p^2\), при \(2\le k<p\) уже вычеркнуто простым множителем числа k, который меньше p. Это не означает, что все меньшие числа уже перечислены.

Изображение: SKopp, версия обновлена Suricata, Wikimedia Commons, CC BY-SA 3.0. Файл не изменён. Иллюстрация охватывает 2–120, а программы ниже используют границу 1000.

Базовая реализация на Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

fn sieve(n: usize) -> Vec<usize> {
    if n < 2 {
        return Vec::new();
    }
    let len = n.checked_add(1).expect("n + 1 is too large");
    let mut is_prime = vec![true; len];
    is_prime[0] = false;
    is_prime[1] = false;

    let mut p = 2;
    while p <= n / p {
        if is_prime[p] {
            let mut multiple = p * p;
            loop {
                is_prime[multiple] = false;
                if n - multiple < p {
                    break;
                }
                multiple += p;
            }
        }
        p += 1;
    }

    (2..=n).filter(|&i| is_prime[i]).collect()
}

fn main() {
    for prime in sieve(1000) {
        println!("{}", prime);
    }
}

Сохраните в sieve.rs и скомпилируйте командой rustc --edition=2021 sieve.rs -o sieve. В Windows задайте имя исполняемого файла sieve.exe. Программа выводит 168 строк: первое число — 2, последнее — 997. Примеры выполнены с Rust 1.90.0.

sieve(0) и sieve(1) возвращают пустой вектор, sieve(2) возвращает [2]. Условие p <= n / p гарантирует, что p * p вычисляется только тогда, когда квадрат не превышает границу. Перед добавлением следующего кратного проверяется оставшееся расстояние. Квадратный корень с плавающей точкой не нужен.

Версия, вычёркивающая только нечётных кандидатов

Чётные числа больше 2 составные. Поэтому можно отметить 2 как истину, а кандидатами сделать только нечётные числа. Квадрат нечётного простого p тоже нечётный; шаг \(2p\) от этого квадрата посещает только нечётные кратные.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

fn sieve_odd(n: usize) -> Vec<usize> {
    if n < 2 {
        return Vec::new();
    }
    let len = n.checked_add(1).expect("n + 1 is too large");
    let mut is_prime = vec![false; len];
    is_prime[2] = true;
    for i in (3..=n).step_by(2) {
        is_prime[i] = true;
    }

    let mut p = 3;
    while p <= n / p {
        if is_prime[p] {
            let step = 2 * p;
            let mut multiple = p * p;
            loop {
                is_prime[multiple] = false;
                if n - multiple < step {
                    break;
                }
                multiple += step;
            }
        }
        p += 2;
    }

    (2..=n).filter(|&i| is_prime[i]).collect()
}

fn main() {
    for prime in sieve_odd(1000) {
        println!("{}", prime);
    }
}

Сохраните эту версию в другом файле и скомпилируйте её. Она выводит те же 168 простых чисел, возвращает пустой результат для 0 и 1, а для 2 — [2]. Не объединяйте две функции main в одном файле.

Эта версия пропускает часть работы с чётными числами. Но инициализация ложью не гарантирует большей скорости. Время зависит от инициализации, записей, обращений к памяти, компилятора и машины. Сравнение измеренных времён здесь не проводится. Массив по-прежнему содержит n + 1 элементов, чтобы индексы непосредственно соответствовали числам.

Сложность и допустимые границы

В обычной RAM-модели решето требует времени \(O(n\log\log n)\) и памяти \(O(n)\) для отметок. Это асимптотические оценки операций и хранения, а не измеренное время или битовая сложность для целых чисел произвольной точности. Задача о решете в материалах Princeton по анализу алгоритмов также приводит этот порядок роста.

Тип bool в Rust занимает один байт, а Vec<T> хранит элементы непрерывно. Этот Vec<bool> не является массивом с побитовой упаковкой. Логическое число отметок — n + 1; метаданные вектора, выделенная ёмкость и возвращаемый Vec<usize> тоже требуют памяти.

Если n + 1 нельзя представить, checked_add возвращает None, а следующий expect вызывает panic. В остальных случаях всё равно нужна достаточная память; произвольно большие границы не поддерживаются. Для больших интервалов можно использовать сегментированное решето. Перечисление простых чисел в диапазоне отличается по назначению от проверки одного большого целого числа.