rust-eratos

为 Rust 语言练习实现的埃拉托斯特尼筛法。

用法

cargo install rust-eratos
rust-eratos 11

Rust 语言适应

本文件的目标

• 针对已掌握 Rust 语言基本知识的初学者
• 通过直接使用语言来熟悉和适应语言。
• 逐步提供可以轻松跟随的小目标。

先决条件

• 应大致了解 Rust 语言的基本语法，或易于查找。
  • 如果这是第一次，请根据个人喜好进行准备。
    • 短小的入门教程 Rust First Steps
    • 长篇优秀的官方社区教程 The Rust Programming Language
    • 在线课程 Exercism: Rust Track
    • 有趣的教程 YouTube: mithradates
• 需要了解素数（质数）的基本算法知识。
• 预先学习不是必需的，可以在跟随过程中查找所需内容。 素数 (数论)

当前阶段需要关注的要点

• 完全掌握基本语法
  • 基本类型、变量、if、match、for、println!、fn、...
• 熟悉基本数据结构
  • 数组、切片、String、Vec、HashMap、元组、...
• 使用语言通用元素
  • struct、enum、trait、iterator、...
• 体验和理解语言特殊元素
  • 所有权、借用、引用、宏、...
• 体验语言生态系统
  • cargo、crates、...
• 这次跟随并不需要使用上述所有内容

现在不需要关注

• 算法改进
• 特定框架的使用方法
• 语言和生态系统的先进功能
  • 泛型、多态、线程、future、async、cargo workspace、...

跟随

• 实现提供的函数内容。
• 如果对算法理解不深或难以思考，可以适当地从文档下方的示例代码中获取灵感。
• 提供的接口有意不包含输入的数 n，但包含它也是无关紧要的。只是保持一致的执行。

n 是否为素数

fn is_prime_number(n: u32) -> bool

• 如果仅使用 if、for 命令实现，尝试使用 match、range、iter、any 等表达式实现。

n 以下的素数数量

fn get_prime_number_count_below(n: u32) -> usize

• 如果仅使用 if、for 命令实现，尝试使用 match、range、iter、filter、count 等表达式实现。
• 如果使用了 filter，与之前使用的 any 相比较，了解类型差异及其原因。
  • 提示：Iterator::next(&mut self) 与新迭代器

n 以下最大的素数

fn get_largest_prime_number_below(n: u32) -> u32

• 如果仅使用 if、for 命令实现，尝试使用 match、range、iter、find、Option<T> 等表达式实现。
• 如果使用了 find，与之前使用的 any、filter 相比较，了解类型差异及其原因。

n 以下的素数

fn get_prime_numbers_below(n: u32) -> Vec<u32>

• 实现埃拉托斯特尼筛法。
• 使用基本数据结构中的 Vec 进行实现。
• 如果只用 if, for 等命令实现，那么尝试用 range, into_iter, filter, collect 等表达式实现。

将命令行输入转换为整数 n

fn parse_args(args: &[String]) -> Result<u32, &'static str>

• 将命令行接收到的字符串转换为整数。
• 使用 Result 适当地返回和处理整数转换结果和错误。

使用编写的功能将输出打印到 stdout。

# output example
> rust-eratos 13

13 is a prime number.
There are 5 prime numbers less than 13, and the largest number is 11.
Prime numbers less than 13.
[2, 3, 5, 7, 11]

尝试更多

• 编写单元测试
• 将实现的功能制作成库
• 缓存计算结果以改进性能
• 分析代码的执行速度并进行改进
• 应用 {2, 3, 5} 轮因式分解算法
  • 轮因式分解算法 链接，更多信息

示例代码

# python

import sys


def is_prime_number(n):
    if n < 2:
        return False

    for i in range(2, int(n ** 0.5) + 1):  # (n ** 0.5) == (math.sqrt(n))
        if n % i == 0:
            return False

    return True


def get_prime_number_count_below(n):
    if n < 3:
        return 0

    count = 0
    for i in range(2, n):
        if is_prime_number(i):
            count += 1

    return count


def get_largest_prime_number_below(n):
    for i in reversed(range(2, n)):
        if is_prime_number(i):
            return i

    return 0


def get_prime_numbers_below(n):
    # sieve = [0, 0] + [i for i in range(2, n)]
    sieve = [0, 0]
    for i in range(2, n):
        sieve.append(i)

    for i in range(2, int(len(sieve) ** 0.5) + 1):
        if sieve[i] <= 0:
            continue

        index = i * i
        while index < len(sieve):
            sieve[index] = 0
            index += i

    primes = []
    for i in range(2, len(sieve)):
        if sieve[i] > 0:
            primes.append(i)

    return primes
    # return [i for i in range(2, len(sieve)) if sieve[i] > 0]


def main(n):
    print(f"{n} is a prime number.")
    print(f"There are {get_prime_number_count_below(n)} prime numbers less than {n},"
          f" and the largest number is {get_largest_prime_number_below(n)}")
    print(f"Prime numbers less than {n}")
    print(get_prime_numbers_below(n))


if __name__ == "__main__":
    main(int(sys.argv[1]))