AtCoder Beginner Contest 400 E

https://atcoder.jp/contests/abc400/tasks/abc400_e

という形の数を全て求めてソートしておきます。そうすれば二分探索が使えます。なので素数は500,000以下でよいです。

// Ringo's Favorite Numbers 3
#![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()
}

fn int_sqrt(n: usize) -> usize {
    let mut x = (n + 1) / 2;
    loop {
        let x1 = (x + n / x) / 2;
        if x1 >= x {
            return x
        }
        x = x1
    }
}


//////////////////// prime ////////////////////

fn make_prime_table(N: usize) -> Vec<usize> {
    let mut a: Vec<bool> = vec![true; N+1];
    for p in 2usize.. {
        if p * p > N {
            break
        }
        else if !a[p] {
            continue
        }
        for n in (p*p..N+1).step_by(p) {
            a[n] = false
        }
    }
    
    (2..N+1).filter(|&n| a[n]).collect::<Vec<usize>>()
}


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

fn collect_even_powers_of_primes(L: usize) -> Vec<(usize, usize)> {
    let primes = make_prime_table(L);
    let mut pows: Vec<(usize, usize)> = vec![];     // [(p^e, p)]
    for &p in primes.iter() {
        let q = p * p;
        let mut n = q;
        while n <= L * L {
            pows.push((n, p));
            if L * L / n < q {
                break
            }
            n *= q
        }
    }
    pows.sort();
    pows
}

fn collect_400numbers(N: usize) -> Vec<usize> {
    let M = int_sqrt(N);
    let pows = collect_even_powers_of_primes(M / 2);
    let mut nums: Vec<usize> = vec![];
    for (i, &(pow1, p1)) in pows.iter().enumerate() {
        for j in i+1..pows.len() {
            let (pow2, p2) = pows[j];
            if p1 == p2 {
                continue
            }
            if N / pow1 < pow2 {
                break
            }
            let num = pow1 * pow2;
            if num > N {
                break
            }
            nums.push(num)
        }
    }
    nums.sort();
    nums
}

fn F_each(q: usize, nums: &Vec<usize>) -> usize {
    let mut first: usize = 0;
    let mut last: usize = nums.len();
    while last - first > 1 {
        let mid = (first + last) / 2;
        if nums[mid] == q {
            return q
        }
        else if nums[mid] < q {
            first = mid
        }
        else {
            last = mid
        }
    }
    nums[first]
}

fn F(Q: usize) {
    let nums = collect_400numbers(1_000_000_000_000);
    for _ in 0..Q {
        let q: usize = read();
        println!("{}", F_each(q, &nums))
    }
}

fn main() {
    let Q: usize = read();
    F(Q)
}