// Copyright (C) 2015 by Alexandru Cojocaru // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this program. If not, see . use std::collections::BitVec; use std::num::Float; //use std::iter::range_step; const maxn: u64 = 10_000_000; fn to_index(n: u64) -> usize { ((n-3)/2) as usize } fn from_index(i: usize) -> u64 { (i*2 + 3) as u64 } // taken from problem 2 fn primes(n: u64) -> Bitv { let mut sieve = Bitv::from_elem(to_index(n) + 1, false); for i in range_step(3, Float::sqrt(n as f64) as u64 + 1, 2) { for j in range_step(i*i, n+1, i*2) { sieve.set(to_index(j), true); } } sieve } fn is_prime(s: &Bitv, n: u64) -> bool { s.get(to_index(n)).unwrap() == false } fn four(s: &Bitv, n: u64) -> Vec { let p1 = 2; let p2 = 2 + n%2; for p3 in range_step(3, n-p1-p2, 2) { if !is_prime(s, p3) { continue; } let p4 = n-p1-p2-p3; if p4 < 3 || !is_prime(s, p4) { continue; } return vec![p1, p2, p3, p4]; } vec![0,0,0,0] } fn main() { let s = &primes(maxn); println!("46 {:?}", four(s, 46)); println!("maxn {:?}", four(s, maxn)); println!("12345 {:?}", four(s, 12345)); }