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

• Q.7 10001st prime

struct Index {
    i: usize,
    _ite: Box<dyn Iterator<Item = usize>>,
}

impl Index {
    fn increment(&mut self) {
        self.i += self._ite.next().unwrap();
    }
    fn new() -> Self {
        Self {
            i: 5,
            _ite: Box::new(vec![2usize, 4].into_iter().cycle()),
        }
    }
}

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

fn main() {
    let mut sieve = [true; 2_000_001];
    let sqrt = ((sieve.len() - 1) as f64).sqrt() as usize;
    let mut sum = 2u64 + 3;
    let mut index = Index::new();
    while index.i <= sqrt {
        if sieve[index.i] {
            sum += index.i as u64;
            rule_out(&mut sieve, index.i);
        }
        index.increment();
    }
    while index.i < sieve.len() {
        if sieve[index.i] {
            sum += index.i as u64;
        }
        index.increment();
    }

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

mod index {
    pub struct Index {
        pub i: usize,
        ite: Box<dyn Iterator<Item = usize>>,
    }
    impl Index {
        pub fn increment(&mut self) {
            self.i += self.ite.next().unwrap();
        }
        pub fn new() -> Self {
            Self {
                i: 5,
                ite: Box::new(vec![2usize, 4].into_iter().cycle()),
            }
        }
    }
}

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

fn main() {
    let mut sieve = [true; 2_000_001];
    let sqrt = ((sieve.len() - 1) as f64).sqrt() as usize;
    let mut sum = 2u64 + 3;
    let mut index = index::Index::new();
    while index.i <= sqrt {
        if sieve[index.i] {
            sum += index.i as u64;
            rule_out(&mut sieve, index.i);
        }
        index.increment();
    }
    while index.i < sieve.len() {
        if sieve[index.i] {
            sum += index.i as u64;
        }
        index.increment();
    }

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

package main

import (
	"fmt"
	"math"
	"testing"
)

type Index struct {
	i int
	f uint8
}

func (i *Index) increment() {
	i.i += 2 << i.f
	i.f ^= 1
}

func ruleout(sieve []bool, p int) {
	for i := p * p; i < len(sieve); i += p {
		sieve[i] = true
	}
}

func Example() {
	n := 2_000_000
	sieve := make([]bool, n+1)
	side := int(math.Sqrt(float64(n)))
	i := Index{i: 5}
	sum := 2 + 3
	for i.i <= side {
		if !sieve[i.i] {
			ruleout(sieve, i.i)
			sum += i.i
		}
		i.increment()
	}
	for i.i < len(sieve) {
		if !sieve[i.i] {
			sum += i.i
		}
		i.increment()
	}

	fmt.Println(sum)
	// Output: 142913828922
}

function assert(condition: any, msg?: string): asserts condition {
  if (!condition) {
    throw new Error(msg);
  }
}

class Index {
  i: number;
  #f: number;
  constructor() {
    this.i = 5;
    this.#f = 0;
  }
  increment() {
    this.i += 2 << this.#f;
    this.#f ^= 1;
  }
}

function ruleout(sieve: boolean[], p: number) {
  for (let i = p * p; i < sieve.length; i += p) {
    sieve[i] = false;
  }
}

const n = 2_000_000;
let sieve = Array(n + 1).fill(true);
const side = Math.sqrt(n) | 0;
let sum = 2 + 3;
const i = new Index();
while (i.i <= side) {
  if (sieve[i.i]) {
    sum += i.i;
    ruleout(sieve, i.i);
  }
  i.increment();
}
while (i.i < sieve.length) {
  if (sieve[i.i]) {
    sum += i.i;
  }
  i.increment();
}
console.log(sum);
assert(sum === 142913828922);