Prime palindrome

/*
 * Given an integer n, return the smallest prime palindrome greater than or equal to n.
 * An integer is prime if it has exactly two divisors: 1 and itself. Note that 1 is not a prime number.
 * For example, 2, 3, 5, 7, 11, and 13 are all primes.
 * An integer is a palindrome if it reads the same from left to right as it does from right to left.
 * For example, 101 and 12321 are palindromes.
 * The test cases are generated so that the answer always exists and is in the range [2, 2 * 108].
 * Example 1:
 * Input: n = 6
 * Output: 7
 * Example 2:
 * Input: n = 8
 * Output: 11
 * Example 3:
 * Input: n = 13
 * Output: 101
 * Constraints:
 * 1 <= n <= 108
 */

fn is_prime_866(n: i64) -> bool {
  if n < 2 { return false; }
  if n == 2 { return true; }
  if n % 2 == 0 { return false; }
  let mut i = 3i64;
  while i * i <= n { if n % i == 0 { return false; } i += 2; }
  true
}

fn make_odd_pal(half: i64, _length: usize) -> i64 {
  let s = half.to_string();
  let rev: String = s[..s.len()-1].chars().rev().collect();
  let full = format!("{}{}", s, rev);
  full.parse().unwrap()
}

impl Solution {
  pub fn prime_palindrome(n: i32) -> i32 {
    // Special case: 11 is the only even-length prime palindrome
    if n <= 11 { return [2,3,5,7,11].iter().copied().find(|&p| p >= n).unwrap(); }
    let n = n as i64;
    // All even-length palindromes > 11 are divisible by 11
    // Generate odd-length palindromes in increasing order
    for length in (1usize..=9).step_by(2) {
      let half = (length + 1) / 2;
      let start: i64 = if half == 1 { 1 } else { 10i64.pow(half as u32 - 1) };
      let end: i64 = 10i64.pow(half as u32);
      for h in start..end {
        let pal = make_odd_pal(h, length);
        if pal >= n && is_prime_866(pal) {
          return pal as i32;
        }
      }
    }
    unreachable!()
  }
}