Question

How to find the largest prime factor of a number in Rust

Answer 1

fn largest_prime_factor(mut n: i64) -> i64 {
    let mut div = 2;
    let mut max_p_fact = -1;

    while n != 0 {
        if n % div != 0 {
            div += 1;
        } else {
            max_p_fact = n;
            n /= div; // Integer division
            if n == 1 {
                break;
            }
        }
    }

    max_p_fact
}

fn main() {
    println!("{}", largest_prime_factor(124));  // 2 x 2 x 31
    println!("{}", largest_prime_factor(288));  // 2 x 2 x 2 x 2 x 2 x 3 x 3
    println!("{}", largest_prime_factor(1288)); // 2 x 2 x 2 x 7 x 23
    println!("{}", largest_prime_factor(100000000)); // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
}



/*
run:

31
3
23
5

*/

 

70+ SQL courses for beginners and professionals

Answer 2

fn largest_prime_factor(mut n: i64) -> i64 {
    let mut largest: i64 = -1;

    // Step 1: Remove all factors of 2
    while n % 2 == 0 {
        largest = 2;
        n /= 2;
    }

    // Step 2: Try odd factors from 3 to sqrt(n)
    let mut i: i64 = 3;
    while i * i <= n {
        while n % i == 0 {
            largest = i;
            n /= i;
        }
        i += 2;
    }

    // Step 3: If n is still > 2, it is a prime number
    if n > 2 {
        largest = n;
    }

    largest
}

fn main() {
    let n1: i64 = 124; // 2 x 2 x 31
    let n2: i64 = 288; // 2 x 2 x 2 x 2 x 2 x 3 x 3
    let n3: i64 = 1288; // 2 x 2 x 2 x 7 x 23
    let n4: i64 = 100000000; // 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 5, 5, 5
    let n5: i64 = 600851475143; // 71, 893, 1471, 6857

    println!("Largest prime factor: {}", largest_prime_factor(n1));
    println!("Largest prime factor: {}", largest_prime_factor(n2));
    println!("Largest prime factor: {}", largest_prime_factor(n3));
    println!("Largest prime factor: {}", largest_prime_factor(n4));
    println!("Largest prime factor: {}", largest_prime_factor(n5));
}


/*
run:

Largest prime factor: 31
Largest prime factor: 3
Largest prime factor: 23
Largest prime factor: 5
Largest prime factor: 6857

*/

 

70+ SQL courses for beginners and professionals