93 lines
2.1 KiB
Rust
93 lines
2.1 KiB
Rust
use num_bigint::BigUint;
|
|
use num_traits::{One, Zero};
|
|
use std::fmt::{Display, Formatter};
|
|
|
|
#[derive(Clone, Debug)]
|
|
pub struct Factors {
|
|
pub number: BigUint,
|
|
pub result: Vec<BigUint>,
|
|
}
|
|
|
|
impl Factors {
|
|
pub fn of(number: BigUint) -> Factors {
|
|
let mut factors = Self {
|
|
number: number.clone(),
|
|
result: Vec::new(),
|
|
};
|
|
|
|
let big_2 = BigUint::from(2u8);
|
|
let big_4 = BigUint::from(4u8);
|
|
|
|
factors.check(&big_2);
|
|
factors.check(&BigUint::from(3u8));
|
|
|
|
let mut divisor = BigUint::from(5u8);
|
|
while &divisor * &divisor <= factors.number {
|
|
factors.check(&divisor);
|
|
divisor += &big_2;
|
|
factors.check(&divisor);
|
|
divisor += &big_4;
|
|
}
|
|
|
|
if factors.number > BigUint::one() {
|
|
factors.result.push(factors.number);
|
|
}
|
|
|
|
factors.number = number; // Restore the number
|
|
factors
|
|
}
|
|
|
|
pub fn is_prime(&self) -> bool {
|
|
self.result.len() == 1
|
|
}
|
|
|
|
fn check(&mut self, divisor: &BigUint) {
|
|
while (&self.number % divisor).is_zero() {
|
|
self.result.push(divisor.clone());
|
|
self.number /= divisor;
|
|
}
|
|
}
|
|
}
|
|
|
|
impl Display for Factors {
|
|
fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
|
|
let mut iter = self.result.iter();
|
|
|
|
match iter.next() {
|
|
None => write!(f, "[]"),
|
|
|
|
Some(first) => {
|
|
write!(f, "[{}", first)?;
|
|
for next in iter {
|
|
write!(f, ", {}", next)?;
|
|
}
|
|
|
|
write!(f, "]")
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn print_factors(number: BigUint) {
|
|
let factors = Factors::of(number);
|
|
|
|
if factors.is_prime() {
|
|
println!("{} -> {} (prime)", factors.number, factors);
|
|
} else {
|
|
println!("{} -> {}", factors.number, factors);
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
print_factors(24u32.into());
|
|
print_factors(32u32.into());
|
|
print_factors(37u32.into());
|
|
|
|
// Find Mersenne primes
|
|
|
|
for n in 2..70 {
|
|
print!("2**{} - 1: ", n);
|
|
print_factors((BigUint::from(2u8) << n) - BigUint::one());
|
|
}
|
|
}
|