fn main() { let v = read_vec::(); let (l, r) = (v[0], v[1]); let primes = get_primes(1000001); let mut flags = vec![true; (r - l) as usize + 1]; let mut numbers = (l..=r).collect::>(); for p in primes { let mut cur = (l / p) * p; if cur < l { cur += p; } while cur <= r { let idx = (cur - l) as usize; let mut count = 0; while numbers[idx] % p == 0 { numbers[idx] /= p; count += 1; } if count >= 2 { flags[idx] = false; } cur += p; } } let mut ans = 0; for num in l..=r { if num == 1 { ans += 1; continue; } if flags[(num - l) as usize] { let (ok, ng) = binary_search(0, num + 1, |m| m * m <= num); if ok * ok != num { ans += 1; } } } println!("{}", ans); } type Input = i128; fn binary_search(lb: Input, ub: Input, criterion: F) -> (Input, Input) where F: Fn(Input) -> bool, { assert_eq!(criterion(lb), true); assert_eq!(criterion(ub), false); let mut ok = lb; let mut ng = ub; while ng - ok > 1 { let mid = (ng + ok) / 2; if criterion(mid) { ok = mid; } else { ng = mid; } } (ok, ng) } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } fn get_primes(n: i128) -> Vec { let mut is_prime = vec![true; n as usize + 1]; let mut primes = Vec::new(); is_prime[0] = false; is_prime[1] = false; for i in 2..n + 1 { if is_prime[i as usize] { primes.push(i); let mut j = 2 * i; while j <= n { is_prime[j as usize] = false; j += i; } } } primes }