Problem 37 "Truncatable primes"
The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.
Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
問 37 「切り詰め可能素数」
3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
fn is_prime(n: u32) -> bool { if n < 2 { return false; } if n == 2 || n == 3 || n == 5 { return true; } for d in &[2u32, 3, 5] { if n % *d == 0 { return false; } } let side = (n as f32).sqrt() as u32; let mut d = 5u32; for i in [2u32, 4].iter().cycle() { d += *i; if d > side { break; } if n % d == 0 { return false; } } true } fn generate_right_truncatable_maybe_prime_numbers(mut p: u32) -> (u32, u32, u32, u32) { p *= 10; (p + 1, p + 3, p + 7, p + 9) } fn is_left_trancatable_prime(p: u32) -> bool { let mut d = 10u32; while d < p { if !is_prime(p % d) { return false; } d *= 10; } true } fn expand_right_truncatable_prime(p: u32, left_truncatable_prime_sum: &mut u32) { if is_left_trancatable_prime(p) { *left_truncatable_prime_sum += p; } let (n1, n2, n3, n4) = generate_right_truncatable_maybe_prime_numbers(p); for &p in [n1, n2, n3, n4].iter().filter(|&n| is_prime(*n)) { expand_right_truncatable_prime(p, left_truncatable_prime_sum); } } fn main() { let mut left_truncatable_prime_sum = 0u32; for &p in [2u32, 3, 5, 7].iter() { expand_right_truncatable_prime(p, &mut left_truncatable_prime_sum); } println!("{}", left_truncatable_prime_sum - 2 - 3 - 5 - 7); assert_eq!(left_truncatable_prime_sum - 2 - 3 - 5 - 7, 748317); }
struct Index { i: usize, _ite: Box<dyn Iterator<Item = usize>>, } impl Index { fn increment(&mut self) { self.i += self._ite.next().unwrap(); } fn new() -> Self { Self { i: 5, _ite: Box::new(vec![2usize, 4].into_iter().cycle()), } } } struct Sieve { _sieve: Vec<bool>, _primes: Vec<usize>, _index: Index, _queue: std::collections::VecDeque<usize>, } impl Sieve { fn rule_out(&mut self, prime: usize) { for i in (prime * prime..self._sieve.len()).step_by(prime) { self._sieve[i] = false; } } fn rule_out_from_previous_position(&mut self, prime: usize, pp: usize) { use std::cmp::max; let begin = max((((pp - 1) / prime) + 1) * prime, prime * prime); for i in (begin..self._sieve.len()).step_by(prime) { self._sieve[i] = false; } } fn clean_sieve(&mut self) { let sqrt = ((self._sieve.len() - 1) as f32).sqrt() as usize; while self._index.i <= sqrt { if self._sieve[self._index.i] { self._primes.push(self._index.i); self._queue.push_back(self._index.i); self.rule_out(self._index.i); } self._index.increment(); } while self._index.i < self._sieve.len() { if self._sieve[self._index.i] { self._primes.push(self._index.i); self._queue.push_back(self._index.i); } self._index.increment(); } } fn new(below: u32) -> Self { assert!(below > 4); let sieve = vec![true; below as usize]; let mut s = Self { _sieve: sieve, _primes: vec![], _index: Index::new(), _queue: std::collections::VecDeque::new(), }; s._queue.push_back(2); s._queue.push_back(3); s.clean_sieve(); s } fn extend(&mut self) { let previous_len = self._sieve.len(); self._sieve.extend(vec![true; previous_len]); for &p in &self._primes.clone() { self.rule_out_from_previous_position(p, previous_len); } self.clean_sieve(); } fn is_prime(&mut self, n: u32) -> bool { if n == 2 || n == 3 { return true; } if n == 0 || n == 1 || n % 2 == 0 || n % 3 == 0 { return false; } while n > self._sieve.len() as u32 - 1 { self.extend(); } self._sieve[n as usize] } fn next_prime(&mut self) -> u32 { loop { if let Some(p) = self._queue.pop_front() { return p as u32; } self.extend(); } } fn is_left_trancatable_prime(&mut self, p: u32) -> bool { let mut d = 10u32; while d < p { if !self.is_prime(p % d) { return false; } d *= 10; } true } fn is_right_trancatable_prime(&mut self, p: u32) -> bool { let mut d = 10u32; while d < p { if !self.is_prime(p / d) { return false; } d *= 10; } true } } fn main() { let mut sum = 0u32; let mut sieve = Sieve::new(10_000); let mut count = 0u8; while count < 15 { let p = sieve.next_prime(); if !sieve.is_left_trancatable_prime(p) { continue; } if !sieve.is_right_trancatable_prime(p) { continue; } count += 1; sum += p; } println!("{}", sum - 2 - 3 - 5 - 7); assert_eq!(sum - 2 - 3 - 5 - 7, 748317); }