第41题-最大素数

本文包含欧拉项目第41题解法

问题描述

第41题图

翻译为中文就是：

如果一个n位的数字包含了1到n的每个数，那么这个数字叫pandigital number（没想好怎么翻译）如：2143十一个4位的pandigital number并且还是素数

求解最大的n位的pandigital prime

解题思路

最初的时候我是打算写一个识别pandigital数的方法，然后迭代遍历是否为素数，这个函数不难写，但是判断效率太慢了，而且如果要遍历一个9位数，计算量非常大，故放弃此方法。后来感觉pandigital数应该不会很多，可以通过排列组合的方式构造一些出来，然后在这个小集合中再判断是否素数

rust语言实现

p41.rs

use algorithms::math::is_prime::is_prime;

pub fn permutate(prefix: &str, s: &str, result: &mut Vec<String>) {
    let n = s.len();
    if n == 0 {
        result.push(prefix.to_owned());
    } else {
        for i in 0..n {
            let s1 = format!("{}{}", prefix.to_owned(), &s[i..=i].to_owned());
            let s2 = format!("{}{}", s[0..i].to_owned(), s[i + 1..n].to_owned());
            permutate(s1.as_str(), s2.as_str(), result);
        }
    }
}

pub fn largest_pandigital_prime() -> usize {
    let mut ns = vec![];
    permutate("", "1234567", &mut ns);
    let mut largest = 0;
    for val in &ns {
        let num = val.parse::<usize>().unwrap();
        if is_prime(num) && num > largest {
            largest = num;
        }
    }
    largest
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_permutate() {
        let mut a = vec![];
        permutate("", "1234", &mut a);
        assert_eq!(24, a.len());
    }

    #[test]
    fn test_largest_pandigital_prime() {
        assert_eq!(7652413, largest_pandigital_prime());
    }
}

代码解释

有2个核心方法，一个是构造字符串全排列的方法，另一个用来判断并且返回最大符合要求的数字。构造全排列的方法很有意思，用了循环加递归，就是说对于一个字符串，提取出其中一个字符，放到首位，然后递归处理剩下的字符，很巧妙的办法，因为我测试了8位9位数字没符合条件的所以为了简便就写死只算7位数的

在编码过程中发现rust处理字符串真是很繁琐，取某个字符，截取指定长度等，使用了&s[i..=i].to_owned()这个小trick来模拟取s[i]位字符