Project Euler 10 - Summation of primes

Question

I'm currently attempting to learn OCaml, and I'm working thought the Project Euler problems to do so. Here's some code I knocked together for problem 10.

I am looking for idiomatic feedback rather than algorithmic

(* 
The sum of the primes below 10 is 2 +たす 3 +たす 5 +たす 7 =わ 17.
Find the sum of all the primes below two million.
MODIFYING CODE FROM PROBLEM 7 
*) 
(* first thing we are going to do is write a bit of code that checks to see if a number is prime *) 
let rec isPrimeRec number start = if (start*start)>number then 1 else if number mod start = 0 then -1 else isPrimeRec number (start+1);;
let i = ref 2;;
let sum = ref 0 in 
while !i <2000000 do 
if (isPrimeRec !i 2) = 1 then 
begin 
sum:= !sum + !i; i:= !i + 1; 
Printf.printf "%d is prime, it is prime number %d\n" !i !sum; 
end 
else 
i:= !i + 1
done;;
let temp = ref 0;;
temp:= isPrimeRec 19 3;
Printf.printf "The value is %d\n" !temp

Now - I almost purposely didn't write this to be efficient algorithmically (for example I am aware that prime numbers can't be even) and there are a few other things that I would change for efficiency - but I'm interested in style feedback - so I'd like the code critiqued much more on the level of "In OCaml, one would normally bracket expression X for readability" or "OCaml let's you use this, clearly syntax instead" - rather than "it's a property of prime numbers that"

Answer 1

Here are some comments and an example rewrite of your code.

Indentation and line breaks are not just idiomatic to OCaml; they are good practices in any language.

A more intuitive type for is_prime would be to have only one argument, so let's encapsulate is_prime_rec:

let is_prime =
 let rec is_prime_rec number start =
 if start * start > number then true (* OCaml provides a type `bool`, distinct from `int`, so it's better to return `true` instead of `1`. *)
 else if number mod start = 0 then false
 else is_prime_rec number (start+1) in
 fun n -> is_prime_rec n 2;;

which yields val is_prime : int -> bool = <fun>.

You know the number of iterations in the loop, so it's better to use for rather than while. This also avoid manually incrementing i.

let sum = ref 0 in
for i = 2 to 2_000_000 do (* detail: OCaml parses `2_000_000` as `2000000`, which is more readable. *)
 if is_prime i then (* no need for parentheses around the if clause *)
 begin
 sum:= !sum + i;
 Printf.printf "%d is prime, it is prime number %d\n" i !sum;
 end
done;;

I can't help but add an algorithmic remark: consider using a sieve.

• Chris: String suggestion: let is_prime = ... in fun n -> is_prime_rec n 2 => let is_prime n = ... in is_prime_rec n 2 But as n doesn't actually change in is_prime_rec it doesn't need to be passed to that function at all.

Answer 2

As has been suggested in another answer, there is no need to use mutable state to accomplish the summation of the primes. However, if you are going to use mutable state, then we might as well use it to achieve algorithmic efficiency by implementing a sieve, which is also suggested in a previous answer.

I am going to make use of sequences (added in OCaml 4.07 - released July 2018) so that the function is as lazy as possible.

let sieve n =
 let arr = Array.make (n + 1) true in
 arr.(0) <- false;
 arr.(1) <- false;
 let rec aux i () =
 if i > n then Seq.Nil
 else if not arr.(i) then aux (i + 1) ()
 else
 let j = ref (i * 2) in
 while !j <= n do
 arr.(!j) <- false;
 j := !j + i
 done;
 Seq.Cons (i, aux (i + 1))
 in
 aux 2

At this point, to get the primes up to two million and sum them becomes:

sieve 2_000_000
|> Seq.fold_left (+) 0

But we might better further leverage sequences to generate the list of indices to mark as false in the sieve. This avoids some imperative code, which generally reduces the opportunities for bugs.

let sieve n =
 let arr = Array.make (n + 1) true in
 arr.(0) <- false;
 arr.(1) <- false;
 let rec aux i () =
 if i > n then 
 Seq.Nil
 else if not arr.(i) then 
 aux (i + 1) ()
 else (
 Seq.ints 2
 |> Seq.take_while (fun j -> i * j <= n)
 |> Seq.iter (fun j -> arr.(i * j) <- false);
 Seq.Cons (i, aux (i + 1))
 )
 in
 aux 2

Answer 3

To complement these very good answers, I would suggest to avoid using refs. The cool thing about functional programming is that it encourages you not to change the states of the variables. In your case, there is no penalty (in terms of performance or readability) not to use refs.

So you could replace the summation loop with a recursive function :

let sumPrimes i =
 let rec aux i sum =
 if (i=1) then sum
 else begin 
 if (isPrimeRec i 2 = 1) then aux (i-1) (sum+i) else aux (i-1) sum
 end
 in aux i 0;;

Which is slightly shorter than :

let i = ref 2;;
let sum = ref 0 in 
while !i <2000000 do 
if (isPrimeRec !i 2) = 1 then 
begin 
sum:= !sum + !i; i:= !i + 1; 
Printf.printf "%d is prime, it is prime number %d\n" !i !sum; 
end 
else 
i:= !i + 1
done;;

And you can finish the problem with a simple :

print_int (sumPrimes 2000000) ;

Answer 4

Hello from Haskell world ;) Consider using some kind of memoization. For example with help of infinte cached sequence through Seq.cache in F#:

let rec is_prime x =
 primes
 |> Seq.takeWhile (fun p -> p*p <= x)
 |> Seq.exists (fun p -> x % p = 0)
 |> not
and primes = 
 seq {
 yield 2;
 yield 3;
 yield!
 Seq.initInfinite (fun i -> i) 
 |> Seq.skipWhile (fun i -> i <= 3)
 |> Seq.filter is_prime
 }
 |> Seq.cache