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

use crate::Solution;
use pmath::primes::{is_prime, sieve_of_eratosthenes};

problem!(Problem0027, 27, "Quadratic Primes");

impl Solution for Problem0027 {
    fn solve(&self) -> String {
        // because n starts from 0, b must be prime
        // so b must only be checked among primes <= 1000
        // for n = 1, 1 + a + b must be prime
        // so a can be calculated as a = some_prime - b - 1
        // since a can be negative, some_prime can be smaller than b
        // in fact some_prime can be as low as 2
        // the upper limit on some_prime is 2000
        // that is because max value of b is 2000 (inclusive), max value of a is 999 and there is also a +1
        // let's first generate a list of primes <= 2000
        let primes_list = sieve_of_eratosthenes(2000);

        // variable to store the maximum number of consecutive primes
        let mut max_consecutive = 0;
        // variable to store the product of a and b that produces the maximum number of consecutive primes
        let mut max_product = 0;

        // b is chosen from primes_list
        // since primes are generated in ascending order;
        // when primes_list[b_ind] > 1000, there is no need to check further
        for b in &primes_list {
            let b = *b as i64;
            if b > 1000 {
                break;
            }

            // for every prime from primes_list calculate a and check the number of consecutive primes
            // if the a is greater than 1000, there is no need to check further
            // because primes are generated in ascending order, next a will be even greater
            for prime in &primes_list {
                let a = *prime as i64 - b - 1;
                if a >= 1000 {
                    break;
                }

                // find the number of consecutive primes
                let mut consecutive_primes = 0;
                for n in 0.. {
                    let polynomial = (n * n) + (a * n) + b;
                    if polynomial < 2 {
                        break;
                    }
                    if is_prime(polynomial as u64).0 {
                        consecutive_primes += 1;
                    } else {
                        break;
                    }
                }

                // if the number of consecutive primes is greater than the previous maximum, update the maximum
                // and store the product of a and b
                if consecutive_primes > max_consecutive {
                    max_consecutive = consecutive_primes;
                    max_product = a * b;
                }
            }
        }

        // return the product of a and b that produces the maximum number of consecutive primes
        max_product.to_string()
    }
}