fn main() { input! { l: u64, r: u64, } let mut p = vec![]; enumerate_prime(7416193, |v| { if v > 2 { p.push(v as u64); } }); for (i, &a) in p.iter().enumerate().take_while(|p| p.1.pow(4) <= r) { for &b in p[i + 1..].iter().take_while(|b| a * a * b.pow(2) <= r) { let m = a * a * b; let mut c = (b + 1).max((l + m - 1) / m); while m * c <= r { if is_prime_miller(c) { println!("{}", m * c); return; } c += 1; } } } println!("-1"); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // ---------- begin miller-rabin ---------- pub fn is_prime_miller(n: u64) -> bool { if n <= 1 { return false; } else if n <= 3 { return true; } else if n % 2 == 0 { return false; } let pow = |r: u64, mut m: u64| -> u64 { let mut t = 1u128; let mut s = (r % n) as u128; let n = n as u128; while m > 0 { if m & 1 == 1 { t = t * s % n; } s = s * s % n; m >>= 1; } t as u64 }; let mut d = n - 1; let mut s = 0; while d % 2 == 0 { d /= 2; s += 1; } const B: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]; for &b in B.iter() { let mut a = pow(b, d); if a <= 1 { continue; } let mut i = 0; while i < s && a != n - 1 { i += 1; a = (a as u128 * a as u128 % n as u128) as u64; } if i >= s { return false; } } true } // ---------- end miller-rabin ---------- // ---------- begin enumerate prime ---------- fn enumerate_prime(n: usize, mut f: F) where F: FnMut(usize), { assert!(1 <= n && n <= 5 * 10usize.pow(8)); let batch = (n as f64).sqrt().ceil() as usize; let mut is_prime = vec![true; batch + 1]; for i in (2..).take_while(|p| p * p <= batch) { if is_prime[i] { let mut j = i * i; while let Some(p) = is_prime.get_mut(j) { *p = false; j += i; } } } let mut prime = vec![]; for (i, p) in is_prime.iter().enumerate().skip(2) { if *p && i <= n { f(i); prime.push(i); } } let mut l = batch + 1; while l <= n { let r = std::cmp::min(l + batch, n + 1); is_prime.clear(); is_prime.resize(r - l, true); for &p in prime.iter() { let mut j = (l + p - 1) / p * p - l; while let Some(is_prime) = is_prime.get_mut(j) { *is_prime = false; j += p; } } for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) { f(i + l); } l += batch; } } // ---------- end enumerate prime ----------