// 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 <http://www.gnu.org/licenses/>.

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<u64> {
	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));
}