Problem 12 "Highly divisible triangular number"

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

問 12 「高度整除三角数」

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

となる.

最初の7項について, その約数を列挙すると, 以下のとおり.

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

struct TriangleNumber {
    _nth: u64,
    _primes: Vec<u64>,
    _num_div_even: u64,
    _num_div_odd: u64,
}

trait Divisors {
    fn number_of_divisors(&self) -> u64;
}

impl TriangleNumber {
    fn new() -> Self {
        Self {
            _nth: 3,
            _num_div_even: 2,
            _num_div_odd: 2,
            _primes: vec![2, 3],
        }
    }
    fn num(&self) -> u64 {
        self._nth * (self._nth + 1) / 2
    }
    fn _divide_fully(&self, n: &mut u64, d: u64, side: &mut u64, count: &mut u64) {
        if *n % d != 0 {
            return;
        }
        let mut exp = 0u64;
        while {
            *n /= d;
            exp += 1;
            *n % d == 0
        } {}
        *side = (*n as f64).sqrt() as u64;
        *count *= exp + 1;
    }
    fn _num_of_divisors(&mut self, mut n: u64) -> u64 {
        let mut count = 1u64;
        let mut side = (n as f64).sqrt() as u64;
        for p in &self._primes {
            if p > side || n == 1 {
                break;
            }
            self._divide_fully(&mut n, p, &mut side, &mut count);
        }
        if n != 1 {
            count *= 2;
            self._primes.push(n);
        }
        count
    }
    fn increment(&mut self) {
        self._nth += 1;
        if self._nth % 2 == 0 {
            self._num_div_odd = self._num_of_divisors(self._nth + 1);
        } else {
            self._num_div_even = self._num_of_divisors((self._nth + 1) / 2);
        }
    }
}

impl Divisors for TriangleNumber {
    fn number_of_divisors(&self) -> u64 {
        self._num_div_even * self._num_div_odd
    }
}

fn main() {
    let mut triangle_number = TriangleNumber::new();
    while triangle_number.number_of_divisors() <= 500 {
        triangle_number.increment();
    }
    let ans = triangle_number.num();

    println!("{}", ans);
    assert_eq!(ans, 76576500);
}