peuler 0.1.0

A Rust crate with solutions to the Project Euler problems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

use crate::Solution;
use itertools::Itertools;
use pmath::digits::{digits, digits_to_int};
use pmath::primes::is_prime;

problem!(Problem0037, 37, "Truncatable Primes");

impl Solution for Problem0037 {
    fn solve(&self) -> String {
        // first digit can only be 2, 3, 5, 7
        // it can't be 4, 6, 8, 9 because then it would be divisible by 2 (or 3)
        // it also can't be 1 because it is not a prime
        // last digit can only be 3, 7
        // it can't be 0, 2, 4, 5, 6, 8 because then the number would be divisible by 2 (or 5)
        // it also can't be 9 because then the number would be divisible by 3
        // and of course it can't be 1 because 1 is not a prime (when truncated)
        // middle digits can be 1, 3, 7, 9
        // they obviously can't be 0, 2, 4, 6, 8 because when truncated that would make the number divisible by 2
        // it also can't be 5 because when truncated that would make the number divisible by 5
        // now candidate numbers can be generated and checked if they are truncatable primes

        // vector to store truncatable primes
        let mut trunc_primes = Vec::with_capacity(TRUNC_PRIMES as usize);

        // start with 2-digit numbers and go up
        'outer: for n_len in 2_usize.. {
            // generate a vector of iterators for each digit
            // first element will be iterator over FIRST_DIGIT
            // middle elements (if any) will be iterator over MIDDLE_DIGIT
            // last element will be iterator over LAST_DIGIT
            let mut iterables = Vec::with_capacity(n_len);
            iterables.push(FIRST_DIGIT.iter().copied());
            for _ in 0..(n_len - 2) {
                iterables.push(MIDDLE_DIGIT.iter().copied());
            }
            iterables.push(LAST_DIGIT.iter().copied());

            // iterate over cartesian product of these iterators over digits (they make numbers)
            for i in iterables.into_iter().multi_cartesian_product() {
                let num = digits_to_int(i.iter().rev(), 10); // convert vector of digits to number

                // check if the number is truncatable prime
                if is_trunc_prime(num) {
                    trunc_primes.push(num);
                    if trunc_primes.len() == TRUNC_PRIMES as usize {
                        break 'outer;
                    }
                }
            }
        }

        // return sum of truncatable primes
        trunc_primes.iter().sum::<u64>().to_string()
    }
}

const TRUNC_PRIMES: u8 = 11;
const FIRST_DIGIT: [u8; 4] = [2, 3, 5, 7];
const MIDDLE_DIGIT: [u8; 4] = [1, 3, 7, 9];
const LAST_DIGIT: [u8; 2] = [3, 7];

/// Check if a number is truncatable prime.
fn is_trunc_prime(x: u64) -> bool {
    if !is_prime(x).0 {
        return false;
    }
    for i in 1..digits(x, 10).len() {
        if !is_prime(x % 10_u64.pow(i as u32)).0 || !is_prime(x / 10_u64.pow(i as u32)).0 {
            return false;
        }
    }
    true
}