use std::convert::TryInto;

/*
Uses Sieve of Eratosthenes with some optimisations:
* Approximates size of the list required using the inverse of an approximation of the prime-counting function to save allocating too much extra space.
* Marks multiples starting from square of current prime.
* Stops marking multiples when the current index is ceil(sqrt(list size)) as the prime before that will be the last prime we need to check multiples for.
* Odd numbers only (wheel factorisation with base 2).

TODO:
* Use bases 2, 3, 5, 7 for wheel factorisation.
* Implement segmented sieve algorithm.
* Multi-thread with Mutex and lazy_static.
* Use bitbox from bitvec for bit compression.
*/

pub fn nth(n: u32) -> u32 {
	if n == 0 {
		return 2;
	}

	// List size approximation is insufficient for values of n = 0, 1, 2, 3, 4, 5, 6, 9, 11 and 12, requiring this correction.
	let corrected_n = (n + match n {
		0 | 11 => 3,
		1 | 5 | 6 | 9 => 4,
		2 | 4 => 6,
		3 => 5,
		7 | 8 | 12 => 1,
		_ => 0,
	}) as f64;
	// Approximated size of the list required using the inverse of an approximation of the prime-counting function, halved (as we're only interested in odd numbers). Lossy cast.
	let list_size = (corrected_n * (corrected_n * corrected_n.ln()).ln() / 2.0).ceil() as usize;
	/*
	Index at which we can stop marking new multiples.
	Array representing list of numbers.
	Prime count.
	 */
	let (limit, mut list, mut count) = (
		// Lossy cast.
		(list_size as f64).sqrt().ceil() as usize,
		vec![true; list_size],
		1,
	);

	for index in 1..limit {
		if list[index] {
			count += 1;
			if count > n {
				// Might panic if values greater than u32::MAX are converted.
				return (index * 2 + 1).try_into().unwrap();
			}
			for multiple in (((index * 2 + 1).pow(2) - 1) / 2..list_size).step_by(index * 2 + 1) {
				list[multiple] = false;
			}
		}
	}
	for index in limit..list_size {
		if list[index] {
			count += 1;
			if count > n {
				// Might panic if values greater than u32::MAX are converted.
				return (index * 2 + 1).try_into().unwrap();
			}
		}
	}

	unreachable!();
}