如何创建一个对各种整数类型通用的 is_prime 函数?

问题描述 投票:0回答:4

我刚刚深入了解 Rust,想要制作一些通用的基本数学函数。我有以下

is_prime
功能:

fn is_prime(n: i64) -> bool {
    if n == 2 || n == 3 {
        return true;
    } else if n % 2 == 0 || n % 3 == 0 {
        return false;
    }

    let mut i = 5i64;
    let mut w = 2i64;
    while i*i <= n {
        if n % i == 0 {
            return false;
        }
        i += w;
        w = 6 - w;
    }
    true
}

我需要什么才能将

isize
i64
usize
等作为参数传递?我已经阅读了主页上的Rust指南,但我不确定如何将特征的想法应用到我的目标中。

rust traits
4个回答
48
投票

通用数字类型使用起来可能相当麻烦,但是一旦掌握了它们的窍门,它们往往不会太糟糕,尽管有点冗长。此类方法的标准构建块是来自 crates.io 的 num

 crate
中的特征,最显着的是 Num
Zero
One
,以及标准库的 
std::cmp::PartialOrd

数字文字不能对任何数字类型通用;它们必须通过特征方法调用来完成;

Zero::zero()

One::one()
 足以满足大多数用途 - 这里我们想要的数字是 0、1、2、3、5 和 6,使用这些构建块完全可以实现。您还可以使用生成这些值的静态方法创建自己的特征,并将其实现为您喜欢的任何数字类型,但仅使用 
Num
 所保证的内容来实现是一个更好的主意。

基本过程是将泛型类型参数指定为基于

Num

(如果您在该类型的值上编写不等式,则为 
PartialOrd
,例如 
i * i <= n
),并将任何数字文字替换为从零构造的数字文字一个,如下面方法开头的六个 
let
 语句所示。这通常就足够了。

以下是此特定方法的最终结果:

// You’ll also need the appropriate dependencies.num addition to Cargo.toml extern crate num; use num::Num; fn is_prime<N: Num + PartialOrd + Copy>(n: N) -> bool { let _0 = N::zero(); let _1 = N::one(); let _2 = _1 + _1; let _3 = _2 + _1; let _5 = _2 + _3; let _6 = _3 + _3; if n == _2 || n == _3 { return true; } else if n % _2 == _0 || n % _3 == _0 { return false; } let mut i = _5; let mut w = _2; while i * i <= n { if n % i == _0 { return false; } i = i + w; w = _6 - w; } true }
    

19
投票
要添加到 Chris Morgan 的答案,您可以使用

num::NumCast::from

 转换为通用数字类型,而使用 
Zero
One
 是不合适的。对于你的情况:

use num::{Num, NumCast}; fn is_prime<N: Num + Ord + NumCast + Copy>(n: N) -> bool { let _0: N = NumCast::from(0usize).unwrap(); let _1: N = NumCast::from(1usize).unwrap(); let _2: N = NumCast::from(2usize).unwrap(); let _3: N = NumCast::from(3usize).unwrap(); let _4: N = NumCast::from(4usize).unwrap(); let _5: N = NumCast::from(5usize).unwrap(); let _6: N = NumCast::from(6usize).unwrap();
    

1
投票
使用 num 包的另一个选项是使用 ToPrimitive 特征将传入的任何类型转换为 i64。使用您提供的相同函数,进行一些修改,以便我们在无法完成到 i64 的转换时返回 None :

use num::ToPrimitive; fn is_prime<N: ToPrimitive>(q: N) -> Option<bool> { let n: i64 = q.to_i64()?; if n == 2 || n == 3 { return Some(true); } else if n % 2 == 0 || n % 3 == 0 { return Some(false); } let mut i = 5i64; let mut w = 2i64; while i * i <= n { if n % i == 0 { return Some(false); } i += w; w = 6 - w; } Some(true) } fn print_is_prime<N: ToPrimitive + std::fmt::Debug + Clone>(q: N) { println!("Is {:?} prime? {:?}", q, is_prime(q.clone())); } fn main() { let prime: usize = 7; print_is_prime(prime); let prime: isize = 7; print_is_prime(prime); let prime: i32 = 7; print_is_prime(prime); let prime: i64 = 7; print_is_prime(prime); }
这给出了输出:

Is 7 prime? Some(true) Is 7 prime? Some(true) Is 7 prime? Some(true) Is 7 prime? Some(true)
    

0
投票
因此,您也可以使用宏来实现此目的,但说实话,最好先使用特定类型编写代码,然后通过用宏类型替换所有相关类型来将其转换为宏。

(顺便说一句,看起来这就是

num

 板条箱所做的。)

如果您坚持使用顶级功能,则必须使用

paste Macro crate 来组成您的名字。

use paste::paste; macro_rules! is_prime_for_x { ($T:ty) => { paste! { named_is_prime_for_x!([<is_prime_ $T>],$T); } }; } // 2 stage macro allows composing the name, with a macro, but doesn't brake formatting macro_rules! named_is_prime_for_x { ($name:ident,$T:ty) => { fn $name(n: $T) -> bool { ... } }; } is_prime_for_x!(u32) // creates fn is_prime_u32(n:u32) is_prime_for_x!(u64) // creates fn is_prime_u64(n:u64) is_prime_for_x!(u128) // creates fn is_prime_u128(n:u128)
如果您想使用类型和泛型为它们命名空间,您甚至可以不使用过去的创建。

struct Primes<T> { primes: Vec<T>, // could store known primes here ;) } macro_rules! impl_primes { ($T:ty) => { impl Primes<$T> { pub fn is_prime(n: $T) -> bool { ... } } }; } impl_primes!(u32); impl_primes!(u64); impl_primes!(u128); fn main() { Primes::<u64>::is_prime(123); }
在二进制文件中它将有多个实现,但似乎主要目标是

不要重复自己(DRY),对吧?

© www.soinside.com 2019 - 2024. All rights reserved.