1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

use getrandom::getrandom;

pub fn rand_usize(index: usize) -> usize {
	let mut new_index = index.to_ne_bytes();
	let err = getrandom(&mut new_index);
	match err {
		Err(err) => println!("Problem generating random usize: {}", err),
		Ok(()) => ()
	};
	usize::from_ne_bytes(new_index)
}

pub fn shuffle_vec (v: &mut Vec<u32>) {
	//For each index, grab a random value stored between that index and the final index
	//(inclusive of current and final indices) then swap that with the current index.
	//If the current index is chosen, it remains the same. (Swaps with itself).
	//Don't add an if statement to check is i == k, it just add cycles in most cases.
	for i in 0..v.len() - 1 {
		let k = i + (rand_usize(i) % (v.len() - i));
		let temp = v[i];
		v[i] = v[k];
		v[k] = temp;
	}
}

pub fn test_prime(sieve: &Vec<u32>, test_prime: &u32) -> bool {
	//A heuristic sqrt(n) search to then logarithmically find how much of the sieve is larger than the sqrt could be good.
	//This does not protect against sieve[-1] being greater than test_prime
	for i in 1..sieve.len() {
		match test_prime % sieve[i] { 
			0 => return false, 
			_ => continue
		}
	}
	true
}

pub fn prime_sieve(n: u32) -> Vec<u32> {
	if n < 2 { return vec!(); }
	
	let mut sieve = vec!(2);
	let mut test_val = 3;
	
	while test_val <= n {
		if test_prime(&sieve, &test_val) { 
			sieve.push(test_val); 
		}
		test_val += 2; 
	}
	
	sieve
}

pub fn factorial(n: u32) -> u128 {
	if n == 0 || n == 1 { return 1; }
	if n == 2 { return 2; }
	if n < 2 {
		let mut fac: u32 = 2;
		for f in 3..n+1 { fac *= f; }
		return u128::from(fac);
	}
	
	let mut fac: u128 = 1;
	let sieve = prime_sieve(n);
	let mut moving_n = n;
	println!("");
	let mut power = 1;
	loop {
		let mut swing_fac:u128 = 1;
		
		for p in sieve.iter() {
			if p > &moving_n { break; }
			let mut q = moving_n;
			let mut f = 1;
			
			while q > 1 {
				q /= p;
				if q & 1 > 0 { f *= p; }
			}
			
			swing_fac *= u128::from(f);
		}
		
		fac *= swing_fac.pow(power);
		power = power << 1;
		
		moving_n = moving_n >> 1;
		if moving_n <= 1 { return u128::from(fac); }
	}
}

#[cfg(test)]
mod tests {
    use super::*;

	#[test]
	fn test_random() {
		for i in 0..10 {
			println!("{}", rand_usize(i));
		}
	}

	#[test]
	fn test_prime_sieve() {
		assert_eq!(prime_sieve(2), vec!(2));
		assert_eq!(prime_sieve(3), vec!(2, 3));
		assert_eq!(prime_sieve(4), vec!(2, 3));
		assert_eq!(prime_sieve(6), vec!(2, 3, 5));
		assert_eq!(prime_sieve(15), vec!(2, 3, 5, 7, 11, 13));
	}
	
	#[test]
	fn test_factorial() {
		let facs = vec!(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600);
		for i in 0..facs.len() {
			assert_eq!(factorial(u32::try_from(i).unwrap()), facs[i]);
		}
	}
}