В этом примере Rust найденные простые числа сохраняются и используются для пробного деления. primes_up_to(max) возвращает список простых чисел до указанной границы включительно. Простых чисел, не превышающих 1000, — 168; 0 и 1 не являются простыми. Это не реализация решета.

Код

 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

fn primes_up_to(max: usize) -> Vec<usize> {
    if max < 2 {
        return Vec::new();
    }
    let mut primes = vec![2];
    let mut n = 3;
    while n <= max {
        let mut is_prime = true;
        for &p in &primes {
            if p > n / p {
                break;
            }
            if n % p == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            primes.push(n);
        }
        if max - n < 2 {
            break;
        }
        n += 2;
    }
    primes
}

fn main() {
    for p in primes_up_to(1000) {
        println!("{}", p);
    }
}

Запуск и малые границы

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

primes_up_to(0) и primes_up_to(1) возвращают пустой вектор; primes_up_to(2) возвращает [2], primes_up_to(3) — [2, 3], а primes_up_to(10) — [2, 3, 5, 7]. Тип параметра usize исключает отрицательные границы. Программа не разбирает стандартный ввод.

Как работают проверка и цикл

1. Если граница меньше 2, верните пустой результат. Иначе сохраните 2 и проверяйте только нечётные кандидаты от 3 до границы. Граница проверяется до обработки кандидата, поэтому при границе 2 число 3 не добавляется.
2. У составного кандидата n есть простой множитель, не превышающий его квадратного корня. Эти простые числа уже находятся в списке благодаря предыдущим кандидатам. Если деление даёт нулевой остаток, отклоните кандидата. Если до выполнения p > n / p делитель не найден, продолжать пробное деление не нужно. Деление положительных целых выражает условие квадратного корня без вычисления p * p или корня с плавающей точкой.
3. for &p in &primes заимствует список, последовательно получает ссылки и копирует каждое значение usize в p. Новое простое число добавляется только после завершения этого цикла. Финальный for p in primes_up_to(1000) извлекает значения из возвращённого вектора и печатает их. Документация Vec в Rust различает итерацию с заимствованием и итерацию, которая забирает владение вектором и потребляет его.
4. Внутри n <= max выражение max - n не может быть отрицательным. Если оставшееся расстояние меньше 2, завершите цикл до сложения; иначе выполните n += 2. Так увеличение не выходит за границу.

Область применения

Исходная программа с фиксированной границей 1000 тоже правильно печатает 168 простых чисел. Однако простая замена границы на 0, 1 или 2 выводит значения 2 или 3 вне диапазона, поскольку граница не проверяется до обработки. Представленная здесь переиспользуемая функция учитывает эти граничные случаи.

Список хранит один usize на каждое найденное простое число. Метаданные вектора и выделенная ёмкость тоже требуют памяти. Грубая верхняя оценка числа делений — O(max sqrt(max)), если считать одно деление одной операцией; это не измеренное время и не битовая сложность. Большие границы требуют больше времени и памяти; быстрая выдача списка для произвольно больших границ не гарантируется. Для больших интервалов см. статью о решете Эратосфена. Это не генератор криптографических простых чисел.