Rust素数筛库primal-sieve的使用，高性能素数生成与质数计算工具

安装

在项目目录中运行以下Cargo命令：

cargo add primal-sieve

或者在Cargo.toml中添加以下行：

primal-sieve = "0.3.7"

使用示例

primal-sieve是一个高性能的素数生成库，提供多种素数相关的计算功能。以下是基本使用示例：

use primal_sieve::Sieve;

fn main() {
    // 创建一个上限为100万的素数筛
    let sieve = Sieve::new(1_000_000);

    // 检查数字是否为素数
    println!("17是素数吗？ {}", sieve.is_prime(17));
    println!("25是素数吗？ {}", sieve.is_prime(25));

    // 获取第100个素数
    println!("第100个素数: {}", sieve.nth_prime(100));

    // 获取小于等于100的素数数量
    println!("≤100的素数数量: {}", sieve.prime_pi(100));

    // 获取小于等于100的所有素数
    println!("≤100的所有素数:");
    for prime in sieve.primes_from(0).take_while(|&p| p <= 100) {
        print!("{} ", prime);
    }
    println!();

    // 分解质因数
    println!("123456的质因数分解:");
    for (prime, exponent) in sieve.factor(123456).unwrap() {
        print!("{}^{} ", prime, exponent);
    }
    println!();
}

完整示例

以下是一个更完整的示例，展示primal-sieve库的主要功能：

use primal_sieve::Sieve;

fn main() {
    // 创建素数筛
    let upper_limit = 10_000_000;
    let sieve = Sieve::new(upper_limit);
    println!("已创建上限为{}的素数筛", upper_limit);

    // 素数测试
    let test_numbers = [2, 17, 25, 31, 100, 997];
    for &n in &test_numbers {
        println!("{}是素数吗？ {}", n, sieve.is_prime(n));
    }

    // 获取第n个素数
    let nth_primes = [1, 10, 100, 1000];
    for &n in &nth_primes {
        println!("第{}个素数: {}", n, sieve.nth_prime(n));
    }

    // 素数计数函数π(x)
    let pi_points = [10, 100, 1000, 10_000];
    for &x in &pi_points {
        println!("π({}) = {}", x, sieve.prime_pi(x));
    }

    // 生成素数序列
    println!("前20个素数:");
    for (i, prime) in sieve.primes_from(0).take(20).enumerate() {
        println!("{}. {}", i+1, prime);
    }

    // 质因数分解
    let numbers_to_factor = [12, 123, 1234, 12345, 123456];
    for &n in &numbers_to_factor {
        print!("{} = ", n);
        let factors = sieve.factor(n).unwrap();
        let mut first = true;
        for (prime, exp) in factors {
            if !first { print!(" × "); }
            first = false;
            if exp == 1 {
                print!("{}", prime);
            } else {
                print!("{}^{}", prime, exp);
            }
        }
        println!();
    }

    // 生成双子素数对
    println!("小于1000的双子素数对:");
    let mut prev_prime = 2;
    for prime in sieve.primes_from(3).take_while(|&p| p < 1000) {
        if prime - prev_prime == 2 {
            println!("({}, {})", prev_prime, prime);
        }
        prev_prime = prime;
    }
}

功能说明

primal-sieve库提供以下主要功能：

素数检测：快速判断一个数是否为素数
素数生成：生成素数序列
素数计数：计算不超过x的素数数量(π(x))
第n个素数：查找第n个素数
质因数分解：将数字分解为质因数乘积形式

该库使用优化的筛法算法，性能优异，适合需要大量素数计算的场景。

itying888 1楼

Rust素数筛库primal-sieve使用指南

介绍

primal-sieve是一个高性能的Rust素数生成和质数计算库，基于优化的埃拉托斯特尼筛法实现。它提供了快速生成素数列表、素数测试、素数计数等功能，特别适合需要处理大量素数计算的场景。

安装

在Cargo.toml中添加依赖：

[dependencies]
primal = "0.3"

主要功能和使用示例

1. 生成素数列表

use primal::Sieve;

fn main() {
    // 创建一个上限为100万的筛子
    let sieve = Sieve::new(1_000_000);
    
    // 获取所有素数
    let primes = sieve.primes_from(0).take(20).collect::<Vec<_>>();
    println!("前20个素数: {:?}", primes);
}

2. 素数测试

use primal::Sieve;

fn main() {
    let sieve = Sieve::new(1_000_000);
    
    println!("17是素数吗？ {}", sieve.is_prime(17));  // true
    println!("25是素数吗？ {}", sieve.is_prime(25));  // false
}

3. 获取第n个素数

use primal::Sieve;

fn main() {
    let sieve = Sieve::new(1_000_000);
    
    // 获取第1000个素数
    let nth_prime = sieve.nth_prime(1000);
    println!("第1000个素数是: {}", nth_prime);  // 7919
}

4. 素数计数函数π(n)

use primal::Sieve;

fn main() {
    let sieve = Sieve::new(1_000_000);
    
    // 计算小于等于1000的素数数量
    let count = sieve.prime_pi(1000);
    println!("小于等于1000的素数有{}个", count);  // 168
}

5. 质因数分解

use primal::Sieve;

fn main() {
    let sieve = Sieve::new(1_000_000);
    
    // 分解数字360
    let factors = sieve.factor(360).unwrap();
    println!("360的质因数分解: {:?}", factors);
    // 输出: [(2, 3), (3, 2), (5, 1)] 表示2³×3²×5¹
}

性能优化技巧

对于重复使用的情况，尽量重用Sieve实例而不是重复创建
根据应用场景合理设置筛子的上限大小
对于非常大的范围，考虑使用primal::StreamingSieve

高级用法：流式筛

use primal::StreamingSieve;

fn main() {
    let mut sieve = StreamingSieve::new();
    
    // 获取第1,000,000个素数
    let big_prime = sieve.nth_prime(1_000_000);
    println!("第1,000,000个素数是: {}", big_prime);  // 15,485,863
}

完整示例代码

以下是一个综合使用primal-sieve库各种功能的完整示例：

use primal::{Sieve, StreamingSieve};

fn main() {
    // 1. 创建普通筛子并生成素数列表
    let sieve = Sieve::new(1_000_000);
    let primes = sieve.primes_from(0).take(20).collect::<Vec<_>>();
    println!("前20个素数: {:?}", primes);

    // 2. 素数测试
    println!("17是素数吗？ {}", sieve.is_prime(17));
    println!("25是素数吗？ {}", sieve.is_prime(25));

    // 3. 获取第n个素数
    let nth_prime = sieve.nth_prime(1000);
    println!("第1000个素数是: {}", nth_prime);

    // 4. 素数计数
    let count = sieve.prime_pi(1000);
    println!("小于等于1000的素数有{}个", count);

    // 5. 质因数分解
    let factors = sieve.factor(360).unwrap();
    println!("360的质因数分解: {:?}", factors);

    // 6. 使用流式筛处理大数
    let mut streaming_sieve = StreamingSieve::new();
    let big_prime = streaming_sieve.nth_prime(1_000_000);
    println!("第1,000,000个素数是: {}", big_prime);

    // 7. 性能测试
    use std::time::Instant;
    let start = Instant::now();
    let _ = Sieve::new(10_000_000);
    println!("创建1000万上限的筛子耗时: {:?}", start.elapsed());
}

这个完整示例展示了：

创建素数筛实例
生成素数列表
素数测试功能
获取第n个素数
素数计数功能
质因数分解
流式筛的使用
简单性能测试

输出示例：

前20个素数: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
17是素数吗？ true
25是素数吗？ false
第1000个素数是: 7919
小于等于1000的素数有168个
360的质因数分解: [(2, 3), (3, 2), (5, 1)]
第1,000,000个素数是: 15485863
创建1000万上限的筛子耗时: 32.3425ms