Even numbers as sum of 2 primes

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:

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:

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.

CategoriesF#

3 Replies to “Even numbers as sum of 2 primes”

1. Carsten says:

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.

2. Ghita says:

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 !

3. Ghita says:

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.