lazy-prime-sieve

Rust 中无限生成素数的惰性埃拉托斯特尼筛法。

使用方法

lazy-prime-sieve 是一个库包。您可以在 Cargo.toml 中添加它，如下所示

[dependencies]
lazy-prime-sieve = "0.1.3"

lazy-prime-sieve 提供了无限生成素数的迭代器。此包提供了一个方便的方法 ::primes()，它返回生成素数的最有效迭代器（在此包中）。

use lazy_prime_sieve::primes;

for i in primes().take(10) {
    println!("{i}");
}

设计

此包提供两种类型的抽象：sieve(s) 和 source(s)。

• source(s) 表示我们从其中抽取素数的无限整数源。
• sieve(s) 从 source(s) 中抽取素数。

两者 source(s) 和 sieve(s) 都实现了 Iterator<Item = u64>。

此包提供了以下筛子

• UnfaithfulSieve：基于经典 Haskell 惰性递归素数筛的非递归 Iterator 的替代方案

  primes = sieve [2..]
  sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]
  

• TrialDivsionSieve：基于模数的记忆化生成素数的方法，这是我们大家都熟悉和喜爱的。
• GenuineSieve：基于优先队列的解决方案，忠实于原始埃拉托斯特尼筛法算法。

此包提供了以下来源

• integer_candidates()：返回一个迭代器，生成序列 2, 3, 4, 5, 6, 7, …
• odds_with_2()：返回一个迭代器，生成序列 2, 3, 5, 7, 9, …
• SpinWheel::default()：单调递增整数的迭代器，不是 2、3、5 和 7 的倍数。

通常，我们用一个 sieve 和一个 source 初始化，并开始生成素数

use lazy_prime_sieve::{sieve::TrialDivisionSieve, source::odds_with_2};

// print the first 10 primes
TrialDivisionSieve::with_source(odds_with_2())
  .take(10)
  .for_each(|x| println!("{x}"));

然而，一些来源从高数字开始。因此，我们需要链接初始素数。

use lazy_prime_sieve::{source::SpinWheel, sieve::GenuineSieve};

// starts from 11
let source = SpinWheel::default();

// print the first 10 primes
[2, 3, 5, 7]
    .iter()
    .cloned()
    .chain(GenuineSieve::with_source(source))
    .take(10)
    .for_each(|x| println!("{x}"));

有关更多详细信息，请参阅文档。

基准测试

此基准测试显示了本库中不同(来源, 筛选)组合（格式："{sieve}_with_{source}"）生成一定数量素数所需的时间。横坐标显示生成的素数数量，纵坐标显示所需时间。

最快的组合是GenuineSieve与SpinWheel::default()。这是lazy_prime_sieve::primes()使用的组合。

请在此处查看生成的基准测试报告这里。

这些基准测试是在分配了8 GB RAM的WSL上的AMD Ryzen 7 x86_64机器上运行的。

参考文献

此库大量借鉴了论文The Genuine Sieve of Eratosthenes。此存储库试图提供基于非递归的Rust迭代器，作为论文中提出的基于Haskell懒惰列表和递归方法的替代方案。

许可证

lazy-prime-sieve采用MIT许可证。有关更多详细信息，请参阅许可证。