#![allow(non_snake_case)] #[allow(unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: usize, } let mut sieve = vec![vec![]; 10_000_010]; for p in 2u32..=10_000_000 { if sieve[p as usize].is_empty() { for q in (p * 2..10_000_010).step_by(p as usize) { sieve[q as usize].push(p); } } } let mut dp = vec![0.; 10_000_010]; for k in 2..=10_000_000 { let mut s = 0.; let mut cnt = 0; for &d in sieve[k].iter() { if sieve[k].len() == 1 { s += dp[d as usize]; cnt += 1; } else if d == sieve[k][0] { let m = sieve[k][1]; s += dp[d as usize] * (m - 1) as f32; cnt += m - 1; } else { let m = sieve[k][0]; s += dp[d as usize] * (m - 1) as f32; cnt += m - 1; } } dp[k] = s + (1 * (k - 1 - cnt as usize)) as f32; dp[k] /= (k - 1) as f32; dp[k] += (k) as f32 / (k - 1) as f32; } println!("{}", dp[N] - 1.); }