Algorithm notes on the back of used envelopes bound in a ring binder

• Q.7 10001st prime
• Q.26 Reciprocal cycles

fn mod_pow(a: u32, exp: u32, m: u32) -> u32 {
    let (mut a, mut exp, m) = (a as u64, exp as u64, m as u64);
    if m == 1 {
        return 0;
    }
    if exp == 0 {
        return 1;
    }
    let mut result = 1;
    a %= m;
    loop {
        if exp % 2 == 1 {
            result *= a;
            result %= m;
        }
        exp >>= 1;
        if exp == 0 {
            break;
        }
        a *= a;
        a %= m;
    }
    result as u32
}

fn gcd(mut a: u32, mut b: u32) -> u32 {
    assert!(a != 0 && b != 0);
    while b != 0 {
        let r = a % b;
        a = b;
        b = r;
    }
    a
}

fn pseudo_fermat_test(n: u32) -> bool {
    gcd(223092870, n) == 1 && mod_pow(223092870, n - 1, n) == 1
}

fn rule_out(sieve: &mut Vec<bool>, prime: usize) {
    for i in (prime * prime..sieve.len()).step_by(prime) {
        sieve[i] = false;
    }
}

fn rule_out_from_previous_position(sieve: &mut Vec<bool>, prime: usize, pp: usize) {
    use std::cmp::max;
    let begin = max((((pp - 1) / prime) + 1) * prime, prime * prime);
    for i in (begin..sieve.len()).step_by(prime) {
        sieve[i] = false;
    }
}

fn extend(sieve: &mut Vec<bool>, primes: &Vec<usize>) {
    let previous_len = sieve.len();
    sieve.extend(vec![true; previous_len]);
    for &p in primes {
        rule_out_from_previous_position(sieve, p, previous_len);
    }
}

fn main() {
    let mut sum = 2u32 + 3;
    let mut sieve = vec![true; 1000];
    let mut primes: Vec<usize> = vec![];
    let mut cursor = 5usize;
    let mut ite = [2usize, 4].iter().cycle();
    'sum_fill: loop {
        while cursor < sieve.len() {
            if !sieve[cursor] {
                cursor += ite.next().unwrap();
                continue;
            }
            &primes.push(cursor);
            rule_out(&mut sieve, cursor);
            sum += cursor as u32;
            if sum >= 1_000_000 {
                sum -= cursor as u32;
                break 'sum_fill;
            }
            cursor += ite.next().unwrap();
        }
        extend(&mut sieve, &primes);
    }

    primes.insert(0, 2);
    primes.insert(1, 3);
    for p in primes {
        sum -= p as u32;
        if pseudo_fermat_test(sum) {
            break;
        }
    }

    println!("{}", sum);
    assert_eq!(sum, 997651);
}

• Fermat primality test, khanacademy
• List of Carmichael numbers

• Q.58 Spiral primes

struct Sieve {
    _sieve: Vec<bool>,
}

impl Sieve {
    fn rule_out(&mut self, prime: usize) {
        for i in (prime * prime..self._sieve.len()).step_by(prime) {
            self._sieve[i] = false;
        }
    }
    fn init(&mut self) {
        let sqrt = (self._sieve.len() as f64).sqrt() as usize;
        let mut index = 5usize;
        for &i in [2usize, 4].iter().cycle() {
            if index > sqrt {
                break;
            }
            if self._sieve[index] {
                self.rule_out(index);
            }
            index += i;
        }
    }
    fn new(below: u32) -> Self {
        assert!(below > 4);
        let sieve = vec![true; below as usize];
        let mut s = Self { _sieve: sieve };
        s.init();
        s
    }
    fn is_prime(&self, n: u32) -> bool {
        assert!(n < self._sieve.len() as u32);
        if n == 2 || n == 3 {
            return true;
        }
        if n == 0 || n == 1 || n % 2 == 0 || n % 3 == 0 {
            return false;
        }
        self._sieve[n as usize]
    }
    fn primes(&self, below: u32) -> Vec<u32> {
        let mut primes = vec![2u32, 3u32];
        let mut index = 5usize;
        for &i in [2usize, 4].iter().cycle() {
            if index >= below as usize {
                break;
            }
            if self._sieve[index] {
                primes.push(index as u32);
            }
            index += i;
        }
        primes
    }
}

fn fill_sum_up_to_million(primes: &[u32]) -> u32 {
    let mut sum = 0u32;
    for &p in primes {
        sum += p;
        if sum > 1_000_000 {
            sum -= p;
            return sum;
        }
    }
    panic!("The prime list was not enough to fill up the sum to be 1 million!");
}

fn main() {
    let sieve = Sieve::new(1_000_000);
    let primes = sieve.primes(1_000_000);
    let mut sum = fill_sum_up_to_million(&primes);
    for p in primes {
        sum -= p;
        if sieve.is_prime(sum) {
            break;
        }
    }

    println!("{}", sum);
    assert_eq!(sum, 997651);
}