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