# Project Euler 10 - Summation of primes

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"

-

Indentation and line breaks are not idiomatic to OCaml, it's good practice 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 better 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.

-

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

-

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

-