Euler problem 5

I am starting to learn Rust and it seems pretty awesome but it's way different than any C based language. I want to know how can I make this code more idiomatic and also how can I improve my solution itself.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

fn near_pow(number:f64, exponent:f64)-> f64
{
exponent.powf(number.log(exponent).floor())
}

fn is_prime(number:i32) -> bool
{
use std::ops::Rem;

if number == 2 { return true; }
if number.rem(2)== 0 { return false; }

let mut i = 3;
while (i*i) <= number
{
if number.rem(i) == 0 {return false;}
i+= 2;
}
true
}

fn euler_problem5(to:i32) -> f64
{
(1..to+1).filter(|&x| is_prime(x))
.fold(1f64, |p , x|p * near_pow(to as f64, x as f64))
}
fn main() {

let x = euler_problem5(20);
println!("{}",x);

}

• You changed the code after you posted it. That makes it kind of difficult to give feedback... – Shepmaster Sep 28 '15 at 15:29
• yes i wasn't sure if i should answer myself or edit. Although i didn't change anything that significant. I am sorry about that. – MAG Sep 28 '15 at 15:32
• anything that significant — except you invalidated one of my points. There's no rush to post your question to Code Review; take your time and make sure that the code you submit the first time is the code you want reviewed. – Shepmaster Sep 28 '15 at 15:36
• FWIW, the filter is better though! – Shepmaster Sep 28 '15 at 15:37
• yes sir you are absolutely right, I will keep that in mind next time :). – MAG Sep 28 '15 at 15:42

1. Rust uses "Egyptian braces" in the majority of cases.

if condition {
// block
} else {
// another block
}

2. Use a space after a : in a type.

fn foo(value: type)

3. Use spaces around operators like ==, +, and * and around symbols like ->.

i += 2;

4. Use a space after a ,.

println!("{}", x);

5. There's no need to use a ; in one-line early return statements (guard clauses).

if number == 2 { return true }

6. Use the % operator instead of calling the rem method:

if number % 2 == 0 { return false }

7. Write the closure to fold inline, especially since you aren't able to give it a better name than fold_op (OP changed the code I am referring to; look in the revision history to see what I'm talking about).

(1..to + 1).fold(1f64, |p, x| {
// stuff
})

8. Whenever possible, try to drive out mutability. I also dislike return statements inside of loop bodies (or really anywhere that aren't guard clauses). Try to use iterators instead.

All together:

fn near_pow(number: f64, exponent: f64) -> f64 {
exponent.powf(number.log(exponent).floor())
}

fn is_prime(number: i32) -> bool {
if number == 2 { return true }
if number % 2 == 0 { return false }

(0..)
.map(|v| 3 + 2 * v) // Can use Range::step_by when stable
.take_while(|i| i * i <= number)
.all(|i| number % i != 0)
}

fn euler_problem5(to: i32) -> f64 {
(1..to + 1).fold(1f64, |p, x| {
if is_prime(x) {
p * near_pow(to as f64, x as f64)
} else {
p
}
})
}

fn main() {
println!("{}", euler_problem5(20));
}

I'm not well-versed on how to do the Euler problems in an efficient way, so hopefully someone else will chime in there.

Update after the original code changed

fn euler_problem5(to: i32) -> f64 {
(1..to + 1)
.filter(|&v| is_prime(v))
.fold(1f64, |p, x| p * near_pow(to as f64, x as f64))
}

user5402 argues to replace floating point with integer operations, but either way you should probably use unsigned integers as you don't need to support negative numbers. This allows you a bit more upper bound to your values as well.

f64

My biggest critique is that you are using floating point arithmetic to solve an integer problem.

Given the possibility for round off error and inexact answers, I would opt for a simple while-loop to compute nearest_pow:

(Sorry - this is Python, I'm not a Rust programmer yet)

def nearest_pow(p,n):
a = 1
while a*p <= n:
a = a * p
return a

Rust has fold and take_while, so I'm sure you can implement this in a functional manner.

This is efficient - it only performs log n iterations - and won't suffer from any round-off errors.

Moreover, it also works for big integers which might come in handy for other number theoretic problems.

Also, I would return the answer as an integer value - perhaps a i64.

• A reasonable suggestion, integer operations will almost always be faster than floating point. However, a literal translation of your sample code seems to differ in results...? Maybe the argument order changed? – Shepmaster Sep 28 '15 at 17:16
• You also need to handle the edge cases of 0 and 1. – Shepmaster Sep 28 '15 at 17:37
• The OP's is_prime function is returning true for p = 1 which could be considered a problem. Alternatively the main loop could just start at 2. – ErikR Sep 28 '15 at 18:53
• Yea you are right forgot about that edge case and I should have started at 2. I knew there was gonna be a lost in precision for big numbers possibly giving a power nearest to x so that x <= b^e, but would this happen in the range of 32 integers? Also could you say my near_pow function is O(1) ? (I am guessing its probably not). – MAG Sep 28 '15 at 23:55