Problem 7 "10001st prime"

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

問 7 「10001番目の素数」

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.

10 001 番目の素数を求めよ.

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 counter = 2u32;
    let mut sieve = vec![true; 10000];
    let mut primes: Vec<usize> = vec![];
    let mut cursor = 5usize;
    let mut ite = [2usize, 4].iter().cycle();
    let n = 'exploration: loop {
        while cursor < sieve.len() {
            if !sieve[cursor] {
                cursor += ite.next().unwrap();
                continue;
            }
            counter += 1;
            if counter == 10001 {
                break 'exploration cursor as u64;
            }
            &primes.push(cursor);
            rule_out(&mut sieve, cursor);
            cursor += ite.next().unwrap();
        }
        extend(&mut sieve, &primes);
    };

    println!("{}", n);
    assert_eq!(n, 104743);
}

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

fn main() {
    let mut n = 0u64;
    let mut counter = 0u32;
    while counter < 10001 {
        n += 1;
        if is_prime(n) {
            counter += 1;
        }
    }
    
    println!("{}", n);
    assert_eq!(n, 104743);
}

package main

import "fmt"

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 ruleoutFromPosition(sieve []bool, prime, position int) {
	pos := (((position - 1) / prime) + 1) * prime
	sq := prime * prime
	if pos < sq {
		pos = sq
	}
	for i := pos; i < len(sieve); i += prime {
		sieve[i] = true
	}
}

func extend(sieve *[]bool, primes []int) {
	previousLen := len(*sieve)
	*sieve = append(*sieve, make([]bool, previousLen)...)
	for _, p := range primes {
		ruleoutFromPosition(*sieve, p, previousLen)
	}
}

func Example() {
	counter := 2
	sieve := make([]bool, 10000)
	primes := []int{}
	i := Index{i: 5}
Exploration:
	for {
		for i.i < len(sieve) {
			if sieve[i.i] {
				i.increment()
				continue
			}
			counter++
			if counter == 10001 {
				break Exploration
			}
			primes = append(primes, i.i)
			ruleout(sieve, i.i)
			i.increment()
		}
		extend(&sieve, primes)
	}
	fmt.Println(i.i)
	// Output: 104743
}

https://stackoverflow.com/questions/23304854/how-do-you-determine-if-a-variable-is-a-slice-or-array

→ Go playground 
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 ruleoutFromPosition(
  sieve: boolean[],
  prime: number,
  position: number,
) {
  const sq = prime * prime;
  const head = (((position - 1) / prime | 0) + 1) * prime;
  for (let i = Math.max(sq, head); i < sieve.length; i += prime) {
    sieve[i] = false;
  }
}

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

function extend(sieve: boolean[], primes: number[]) {
  const previousLen = sieve.length;
  sieve.push(...Array(previousLen).fill(true));
  for (const p of primes) {
    ruleoutFromPosition(sieve, p, previousLen);
  }
}

let counter = 2;
let sieve = Array(10000).fill(true);
let primes = [];
const i = new Index();
exploration:
while (true) {
  while (i.i < sieve.length) {
    if (!sieve[i.i]) {
      i.increment();
      continue;
    }
    counter++;
    if (counter === 10001) {
      break exploration;
    }
    primes.push(i.i);
    ruleout(sieve, i.i);
    i.increment();
  }
  extend(sieve, primes);
}
console.log(i.i);
assert(i.i === 104743);
→ TypeScript playground