素数表を使わない約数の列挙

自然数$n$に対する全ての約数を列挙します。

$O(\sqrt{n})$

$1$ から $\sqrt{n}$ をとる $i$ に対して $n := i * x$ が成り立つ $i$ と $x$ を格納します。

また、

$n = i_k * x_k$ とおくと、 $i_k > \sqrt{n}$ の時、 $i_k$ はすでに $\exists x_t$ $(0 \leq t < k)$ において探索されているので

$i \leq \sqrt{n}$ まで探索すればよいことがわかります

Rust

fn divisors(n: usize) -> Vec<usize> {
    let mut divisors = Vec::new();
    // n := i * x とおくと、 i が i > root(n) の時、　i はすでに ある x に探索されているから
    // i <= root(n) まで探索すればよい
    for i in 1..=(f64::sqrt(n as f64) + 1e-9) as usize {

        // i で n が割り切れた場合
        if n % i == 0 {
            // 約数リストに格納
            divisors.push(i);

            // n := i * x の x を格納。ただし x := i の時は除く
            if i != n / i {
                divisors.push(n / i);
            }
        }
    }
    divisors.sort();
    divisors
}


fn main() {
   assert_eq!(vec![1, 2, 3, 4, 6, 8, 12, 24], divisiors(24));
}

参考

Quora
唯物是真 @Scaled_Wurm