# Largest Prime factor (Project Euler in Rust)

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));
}


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.