5
\$\begingroup\$

I've been working on my Rust a bit and want to know how idiomatic my rust code is for the following Project Euler problem: What is the largest prime factor of the number 600851475143 ?

I'm not looking for ways to improve efficiency or how to improve the strategy, but purely what I can improve with my Rust technique. There's two files: src/prime/sieve.rs which has a function for generating a vector of prime numbers, and src/p003.rs which is where the problem is solved.

// src/prime/sieve.rs

pub fn sieve(ceil: usize) -> Vec<usize> {
    let mut is_prime = vec![true; ceil + 1];
    is_prime[0] = false;
    if ceil >= 1 {
        is_prime[1] = false
    }

    for num in 2..ceil + 1 {
        if is_prime[num] {
            let mut factor = num * num;
            while factor <= ceil {
                is_prime[factor] = false;
                factor += num;
            }
        }
    }

    is_prime
        .iter()
        .enumerate()
        .filter_map(|(p, &is_p)| if is_p { Some(p) } else { None })
        .collect()
}
// src/prime/mod.rs

pub mod sieve;
// src/p003.rs

// https://projecteuler.net/problem=3
mod prime;
use prime::sieve::sieve;

fn biggest_prime_factor(n: usize) -> usize {
    for p in sieve((600851475143_f32.sqrt()) as usize).iter().rev() {
        if n % *p == 0 {
            return *p;
        }
    }
    return 0;
}

fn main() {
    println!("{}", biggest_prime_factor(600851475143));
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I think

    for p in sieve((600851475143_f32.sqrt()) as usize).iter().rev() {

should be

    for p in sieve(((n as f32).sqrt()) as usize).iter().rev() {

Alternative approach

You could chain an iterator in runtime:

#[test]
fn main_playground() {
    // Sieve iterator-style
    let number: u128 = 600851475143;
    let upper_limit: u128 = (number as f32).sqrt().floor() as _;

    let mut sieve: Box<dyn Iterator<Item = _>> = Box::new(2..=upper_limit);

    while let Some(prime_number) = sieve.next() {
        sieve = Box::new(sieve.filter(move |&x| x % prime_number != 0));
        if number % (prime_number as u128) == 0 {
            dbg!(prime_number);
        }
    }
}

The answer is still 6857. But output is

running 1 test
[src\problem_003.rs:12] prime_number = 71  
[src\problem_003.rs:12] prime_number = 839 
[src\problem_003.rs:12] prime_number = 1471
[src\problem_003.rs:12] prime_number = 6857

I can think of many more approaches to this. I'd actually build a Sieve iterator if I were you.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.