use std::collections::HashMap; #[allow(unused_imports)] use std::io::Write; // {{{1 #[allow(unused)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()); } #[allow(unused)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()); } macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut 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_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_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, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // }}} fn main() { input! { x: usize, } let solve = Solve::new(); let sqrt = (x as f64).sqrt() as usize; let mut v = vec![]; let mut min = std::isize::MAX; for i in 1..x { let a = i; let b = x - i; if (a as isize - b as isize).abs() > 2 * sqrt as isize + 1 { continue; } let tmp = (solve.f(a) as isize - solve.f(b) as isize).abs(); if tmp == min { v.push((a, b)); } else if tmp < min { min = tmp; v = vec![(a, b)]; } } for (a, b) in v { println!("{} {}", a, b); } } struct Solve { primes: Vec, } impl Solve { fn new() -> Solve { let n = 2_000_000; let primes = prime_sieve((n as f64).sqrt() as usize); Solve { primes } } fn prime_factor(&self, n: usize) -> HashMap { let mut factors = HashMap::new(); let primes = &self.primes; let mut rest = n; for &p in primes { while rest % p == 0 { let count = factors.entry(p).or_insert(0); *count += 1; rest /= p; } } if rest != 1 { factors.insert(rest, 1); } factors } fn f(&self, n: usize) -> usize { let factors = self.prime_factor(n); let mut d = 1; for (_, e) in factors { d *= e + 1; } n - d } } fn prime_sieve(n: usize) -> Vec { let mut table: Vec = vec![0; (n + 1) as usize]; let mut primes: Vec = Vec::new(); for i in 2..(n + 1) { if table[i as usize] == 0 { primes.push(i); for j in 2..n { if i * j > n { break; } table[(i * j) as usize] = 1 } } } primes }