Struct Prime 

pub struct Prime {}

A struct that provides methods for prime factorization using pollard rho algorithm and testing primality of numbers.

Implementations

impl Prime

pub fn pollard(n: u64) -> u64

Pollard’s rho algorithm for integer factorization.

Arguments

• n - The number to factorize.

Returns

A non-trivial factor of n.

Time Complexity

The algorithm offers a trade-off between its running time and the probability that it finds a factor. A prime divisor can be achieved with a probability around 0.5, in O(?d) <= O(n^(1/4)) iterations. This is a heuristic claim, and rigorous analysis of the algorithm remains open.

pub fn factor(n: u64) -> Vec<u64>

Factorizes n into its prime factors.

Arguments

• n - The number to factorize.

Returns

A vector containing the prime factors of n in sorted order.

pub fn is_prime(n: u64) -> bool

Checks if n is a prime number.

Arguments

• n - The number to check.

Returns

true if n is prime, false otherwise.