A very old unsolved problem in numbers theory, known as Goldbach’s conjecture, says that any even number greater than 5 can be written as the sum of 2 prime numbers. It hasn’t been solver yet, not I will try to solve it. But I decided to write some F# code to display all the possibilities of writing an even number as the sum of two primes. This turned to be quite simple actually:
First, I wrote a function that checks if a number is prime:
|
1 2 |
let is_prime n = not ([2..n/2] |> Seq.filter (fun x -> (n % x) = 0) |> Seq.nonempty) |
Then it was all about checking all the numbers from 2 to N/2 to see if k and N-k are both primes and if so print them:
|
1 2 3 4 |
let check n = [2..n/2] |> Seq.filter (fun x -> (is_prime x) && (is_prime (n-x))) |> Seq.iter (fun x -> printfn "%d & %d" x (n-x)) |
For instance, if we consider number 200, the check function would print:
3 & 197
7 & 193
19 & 181
37 & 163
43 & 157
61 & 139
73 & 127
97 & 103
And that’s about it; though you can imagine optimizing this by caching the prime numbers already computed. But that wasn’t something I wanted to consider for this problem.
Hi,
aside from optimizing by memoizing the primes (which would make this somewhat unreadable) you can improve performance if you not check all numbers from 2 to n/2 but only numbers from 2 to sqrt(n) in your prim-tester.
This approach (using seq) is very memory intensive for big numbers. This is a pitty considering the flexibility offered by seq and the fact that is lazy evaluated. Is there something that can be done on the same line so as to be able to apply the algorithm to bigger numbers (speed not a constraint) ? In a tipical imperative implementation the memory consumption would not be a constraint and it would be nice to see a functional approach here that works with bigger numbers also…
BTW: great work !
Discovered an issue related to memmory consumption here. The problem is that [ 1 .. n/2] is an array and not a sequence -> eats up more memory than needed for our problem: { 1 .. n/2 } should fix it