Rust素数计算库slow_primes使用指南

简介

slow_primes是Rust中一个专注于素数相关计算的库，提供了高效的素数生成、分解和素性测试功能。虽然名字中有"slow"，但实际上它提供了相当高效的实现。

安装

在Cargo.toml中添加依赖：

[dependencies]
slow_primes = "0.1"

主要功能

1. 素数生成

use slow_primes::Primes;

fn main() {
    // 生成前100个素数
    let primes = Primes::sieve(100);
    println!("前100个素数: {:?}", primes.primes());
    
    // 生成直到100的所有素数
    let primes_up_to_100 = Primes::sieve(100);
    println!("直到100的所有素数: {:?}", primes_up_to_100.primes());
}

2. 素性测试

use slow_primes::is_prime;

fn main() {
    let num = 104729; // 第10000个素数
    
    if is_prime(num) {
        println!("{} 是素数", num);
    } else {
        println!("{} 不是素数", num);
    }
}

3. 因数分解

use slow_primes::factorise;

fn main() {
    let num = 123456789;
    let factors = factorise(num);
    
    println!("{} 的质因数分解: {:?}", num, factors);
    // 输出: 123456789 的质因数分解: [(3, 2), (3607, 1), (3803, 1)]
}

4. 获取第n个素数

use slow_primes::nth_prime;

fn main() {
    let n = 1000;
    let prime = nth_prime(n);
    
    println!("第{}个素数是: {}", n, prime);
}

5. 素数迭代器

use slow_primes::Primes;

fn main() {
    let mut primes = Primes::all();
    
    // 打印前10个素数
    for _ in 0..10 {
        println!("{}", primes.next().unwrap());
    }
}

性能提示

1. 对于需要多次素数检查的应用，先创建一个Primes实例并重复使用它，比每次都调用独立函数更高效。

2. 对于大数分解，可以先检查数是否很小，因为小数的分解有优化路径。

3. 素性测试对于非常大的数(>2^64)可能会变慢，这时可以考虑概率性测试。

示例：寻找孪生素数

use slow_primes::Primes;

fn find_twin_primes(limit: usize) {
    let primes = Primes::sieve(limit);
    let prime_list = primes.primes();
    
    for window in prime_list.windows(2) {
        if window[1] - window[0] == 2 {
            println!("孪生素数对: ({}, {})", window[0], window[1]);
        }
    }
}

fn main() {
    find_twin_primes(1000);
}

完整示例：素数应用综合演示

use slow_primes::{Primes, is_prime, factorise, nth_prime};

fn main() {
    // 1. 素数生成演示
    println!("=== 素数生成演示 ===");
    let primes = Primes::sieve(100);
    println!("前50个素数: {:?}", &primes.primes()[..50]);
    
    // 2. 素性测试演示
    println!("\n=== 素性测试演示 ===");
    let test_numbers = [2, 15, 17, 100, 104729];
    for &num in &test_numbers {
        println!("{} 是素数吗? {}", num, is_prime(num));
    }
    
    // 3. 因数分解演示
    println!("\n=== 因数分解演示 ===");
    let numbers_to_factor = [15, 100, 12345];
    for &num in &numbers_to_factor {
        println!("{} 的质因数分解: {:?}", num, factorise(num));
    }
    
    // 4. 获取第n个素数
    println!("\n=== 获取第n个素数 ===");
    let positions = [1, 10, 100, 1000];
    for &n in &positions {
        println!("第{}个素数是: {}", n, nth_prime(n));
    }
    
    // 5. 寻找孪生素数
    println!("\n=== 寻找孪生素数 ===");
    find_twin_primes(1000);
}

fn find_twin_primes(limit: usize) {
    let primes = Primes::sieve(limit);
    let prime_list = primes.primes();
    
    println!("在{}以内的孪生素数对有:", limit);
    for window in prime_list.windows(2) {
        if window[1] - window[0] == 2 {
            println!("({}, {})", window[0], window[1]);
        }
    }
}

slow_primes库虽然名称谦虚，但提供了强大而实用的素数相关功能，适合需要素数操作的数学计算和密码学应用。