Problem 47 "Distinct primes factors"

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

問 47 「異なる素因数」

それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:

14 = 2 × 7

15 = 3 × 5

それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:

644 = 22 × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19

最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?

struct Sieve {
    _sieve: Vec<bool>,
    _count: Vec<u8>,
    _primes: Vec<usize>,
    _cursor: usize,
}

impl Sieve {
    fn rule_out(&mut self, prime: usize) {
        for i in (prime..self._sieve.len()).step_by(prime) {
            self._sieve[i] = false;
            self._count[i] += 1;
        }
    }
    fn rule_out_from_previous_position(&mut self, prime: usize, pp: usize) {
        let begin = (((pp - 1) / prime) + 1) * prime;
        for i in (begin..self._sieve.len()).step_by(prime) {
            self._sieve[i] = false;
            self._count[i] += 1;
        }
    }
    fn is_start_of_four_consective_nums_with_factors(&self) -> bool {
        let i = self._cursor;
        if self._count[i] != 4 {
            return false;
        }
        if self._count.len() - 1 < i + 3 {
            return false;
        }
        self._count[i + 1] == 4 && self._count[i + 2] == 4 && self._count[i + 3] == 4
    }
    fn clean_sieve_with_exploration(&mut self) -> Option<u32> {
        while self._cursor < self._sieve.len() {
            if self._sieve[self._cursor] {
                self._primes.push(self._cursor);
                self.rule_out(self._cursor);
                continue;
            }
            if self.is_start_of_four_consective_nums_with_factors() {
                return Some(self._cursor as u32);
            }
            self._cursor += 1;
        }
        None
    }
    fn new(below: u32) -> Self {
        assert!(below > 4);
        let sieve = vec![true; below as usize];
        let count = vec![0u8; below as usize];
        Self {
            _sieve: sieve,
            _count: count,
            _primes: vec![],
            _cursor: 2,
        }
    }
    fn extend(&mut self) {
        let prev_len = self._sieve.len();
        self._sieve.extend(vec![true; self._sieve.len()]);
        self._count.extend(vec![0u8; self._count.len()]);
        let primes = self._primes.clone();
        for &p in primes.iter() {
            self.rule_out_from_previous_position(p, prev_len);
        }
    }
}

fn main() {
    let mut sieve = Sieve::new(10_000);
    let n = loop {
        if let Some(n) = sieve.clean_sieve_with_exploration() {
            break n;
        }
        sieve.extend();
    };

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