Problem 41 "Pandigital prime"

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

問 41 「パンデジタル素数」

n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする. #下のリンク先にあるような数学的定義とは異なる

例えば2143は4桁 パンデジタル数 であり, かつ素数である.

n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ.

fn consume(usable_items: &Vec<u32>, accumulated_num: u32, drain: &mut Vec<u32>) {
    if usable_items.len() == 0 {
        drain.push(accumulated_num);
        return;
    }
    for i in 0..usable_items.len() {
        let mut items = usable_items.clone();
        let mut num = accumulated_num.clone();
        let n = items.remove(i);
        num *= 10;
        num += n;
        consume(&items, num, drain);
    }
}

fn permutations(n: u32) -> Vec<u32> {
    let items = (1..=n).into_iter().rev().collect::<Vec<u32>>();
    let capacity = items.iter().map(|&i| i).product::<u32>() as usize;
    let mut drain = Vec::with_capacity(capacity);
    consume(&items, 0, &mut drain);
    drain
}

fn is_prime(n: u32) -> bool {
    if n < 2 {
        return false;
    }
    if n == 2 || n == 3 || n == 5 {
        return true;
    }
    for d in &[2u32, 3, 5] {
        if n % *d == 0 {
            return false;
        }
    }
    let side = (n as f32).sqrt() as u32;
    let mut d = 5u32;
    for i in [2u32, 4].iter().cycle() {
        d += *i;
        if d > side {
            break;
        }
        if n % d == 0 {
            return false;
        }
    }
    true
}

fn main() {
    let mut p = None;
    'exploration: for &d in [7, 4].iter() {
        for n in permutations(d) {
            if is_prime(n) {
                p = Some(n);
                break 'exploration;
            }
        }
    }

    println!("{:?}", p);
    assert_eq!(p, Some(7652413));
}