primal

primal将原始力量融入素数。

这个crate包括：

• 优化的素数筛
• 检查素性
• 枚举素数
• 分解数字
• 估计π(n)（小于n的素数数量）和p_k（第k个素数）的上下界

这使用最先进的缓存友好的欧几里得筛法来枚举到某个固定界限的素数（以内存高效的方式），然后允许使用缓存信息进行诸如枚举和计数素数等操作。

primal在作者的笔记本电脑（i7-3517U）上计数小于10^10的素数数量（455052511）大约需要2.8秒和少于3MB的RAM。

文档

lib.rs:

primal将原始力量融入素数。

这个crate包括：

• 优化的素数筛
• 检查素性
• 枚举素数
• 分解数字
• 估计π(n)（小于n的素数数量）和p_k（第k个素数）的上下界

这使用最先进的缓存友好的欧几里得筛法来枚举到某个固定界限的素数（以内存高效的方式），然后允许使用缓存信息进行诸如枚举和计数素数等操作。

primal在我的笔记本电脑（i7-3517U）上计数小于10^10的素数数量（455052511）大约需要2.8秒和少于3MB的RAM。

源代码

使用这个库

只需将以下内容添加到你的Cargo.toml

[dependencies]
primal = "0.2"

示例

索引素数

让我们找到第10001个素数。最简单的方法是枚举素数，并找到第10001个

// (.nth is zero indexed.)
let p = primal::Primes::all().nth(10001 - 1).unwrap();
println!("The 10001st prime is {}", p); // 104743

在我的计算机上，这需要大约400微秒，看起来不错且快速，但，Primes以性能为代价提供了灵活性：我们可以让它更快。StreamingSieve类型提供了一个专门的nth_prime函数

let p = primal::StreamingSieve::nth_prime(10001);
println!("The 10001st prime is {}", p); // 104743

这只需要10微秒！StreamingSieve非常高效，并且使用的内存非常少。这是用primal解决此任务的最佳方式。

既然那么简单，现在让我们加大难度：找到第100,000个、200,000个、300,000个，...，第10,000,000个质数（共100个）的和。

我们可以反复调用 StreamingSieve::nth_prime。

// the primes we want to find
let ns = (1..100 + 1).map(|x| x * 100_000).collect::<Vec<_>>();

// search and sum them up
let sum = ns.iter()
            .map(|n| primal::StreamingSieve::nth_prime(*n))
            .fold(0, |a, b| a + b);
println!("the sum is {}", sum);

这大约需要1.6秒来打印结果 the sum is 8795091674；速度并不快。每次调用 nth_prime 都非常快（100,000个需要400微秒，而10,000,000个需要40毫秒），但累积起来就不好了。每次调用都是从零开始，重复之前的调用所做的工作...如果能直接用10,000,000的结果来复用小数的结果那岂不是很好？

Sieve 类型是 StreamingSieve 的封装，它缓存信息，允许重复查询以高效地回答。

有一个问题：Sieve 需要一个限制来知道筛选的边界：我们需要一种方法来找到一个上界，确保它至少和我们的所有质数一样大。我们可以猜测，比如10¹⁰ 足够大，并使用它，但这是一个巨大的高估（剧透：第10,000,000个质数大约是2×10⁸）。我们也可以尝试用指数级增长的上界进行过滤，直到找到一个合适的，或者，我们可以通过更深入的数学方法estimate_nth_prime 来简化这个过程。

// the primes we want to find
let ns = (1..100 + 1).map(|x| x * 100_000).collect::<Vec<_>>();

// find our upper bound
let (_lo, hi) = primal::estimate_nth_prime(10_000_000);

// find the primes up to this upper bound
let sieve = primal::Sieve::new(hi as usize);

// now we can efficiently sum them up
let sum = ns.iter()
            .map(|n| sieve.nth_prime(*n))
            .fold(0u64, |a, b| a + b as u64);
println!("the sum is {}", sum);

这大约需要40毫秒，并给出相同的结果：好多了！

（顺便说一下，使用10¹⁰作为边界而不是更准确的估计，仍然只需要大约3秒。）

计算质数

另一个问题是：计算1百万以下的质数数量。这是评估质数计数函数π，即π(10⁶)。

像上面一样，有几种方法可以解决这个问题：迭代器和筛选器。

const LIMIT: usize = 1_000_000;

// iterator
let count = primal::Primes::all().take_while(|p| *p < LIMIT).count();
println!("there are {} primes below 1 million", count); // 78498

// sieves
let sieve = primal::Sieve::new(LIMIT);
let count = sieve.prime_pi(LIMIT);
println!("there are {} primes below 1 million", count);

let count = primal::StreamingSieve::prime_pi(LIMIT);
println!("there are {} primes below 1 million", count);

StreamingSieve 速度最快（380微秒），其次是 Sieve（400），而 Primes 在1300微秒后排在最后。当然，使用 Sieve 的重复查询会比使用 StreamingSieve 快，但这种灵活性是以额外的内存使用为代价的。

如果只需要近似值，estimate_prime_pi 提供了接近的上界和下界

let (lo, hi) = primal::estimate_prime_pi(1_000_000);
println!("there are between {} and {} primes below 1 million", lo, hi);
// 78380, 78573

搜索质数

现在有一个地方可能用到 Primes：找到第一个二进制展开（不包括尾随零）以 00..001 结尾的质数，至少有27个零。这个条件通过以下方式检查：

fn check(p: usize) -> bool {
    p > 1 && (p / 2).trailing_zeros() >= 27
}

let p = primal::Primes::all().find(|p| check(*p)).unwrap();
println!("the prime is {}", p);

let p;
let mut lower_bound = 1 << (27 + 1);
loop {
    // our upper bound is double the lower bound
    let sieve = primal::Sieve::new(lower_bound * 2);
    if let Some(p_) = sieve.primes_from(lower_bound).find(|p| check(*p)) {
        p = p_;
        break
    }
    lower_bound *= 2;
}
println!("the prime is {}", p);

let mut p = 0;
for k in 1.. {
    p = k * (1 << (27 + 1)) + 1;
    if primal::is_prime(p) { break }
}
println!("the prime is {}", p);