Skip to content

Instantly share code, notes, and snippets.

@madprops
Created August 5, 2019 02:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save madprops/0c714b86419947614f65e119624bf45c to your computer and use it in GitHub Desktop.
Save madprops/0c714b86419947614f65e119624bf45c to your computer and use it in GitHub Desktop.
Quick Rust algorithm to find prime factors of a number
fn fac(n: u64) -> Vec<u64>
{
let step = |x| (1 + ((x << 2) as i32) - (((x >> 1) as i32) << 1)) as u64;
let maxq: u64 = (n as f64).sqrt().floor() as u64;
let mut d = 1;
let mut q = if n % 2 == 0 {2} else {3};
while q <= maxq && n % q != 0
{
q = step(d);
d += 1;
}
if q <= maxq
{
let mut v: Vec<u64> = vec![q];
v.extend(fac(n / q));
return v;
}
else
{
let v: Vec<u64> = vec![n];
return v;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment