AtCoder Beginner Contest 284 D

https://atcoder.jp/contests/abc284/tasks/abc284_d

までにpかqのどちらかで割り切れます。
qで割り切れたら、を計算します。の計算はニュートン法的に、
, を収束するまで繰り返します。

// Happy New Year 2023
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn read_input() -> Vec<u64> {
    let T: usize = read();
    (0..T).map(|_| read()).collect::<Vec<u64>>()
}

fn int_sqrt_core(u: u64, s0: u64) -> u64 {
    let s = (s0 + u / s0) / 2;
    if s >= s0 {
        s0
    }
    else {
        int_sqrt_core(u, s)
    }
}

fn int_sqrt(n: u64) -> u64 {
    int_sqrt_core(n, n)
}

fn f(n: u64) -> (u64, u64) {
    for p1 in 2u64.. {
        if n % p1 == 0 {
            if n % (p1 * p1) == 0 {
                return (p1, n / (p1 * p1))
            }
            else {
                let q = p1;
                return (int_sqrt(n / q), q)
            }
        }
    }
    (0, 0)  // ここには来ないが要る
}

fn main() {
    let N = read_input();
    for n in N.into_iter() {
        let (p, q) = f(n);
        println!("{} {}", p, q)
    }
}