Chase The Limit

For this post, i’ll write it in english instead indonesian language. So, if there are so many gramatical error, you can contact me so i can fix it. Thank You..

In this problem, You are asked to verify Goldbach’s Conjecture for all even numbers less than a million.

What is Goldbach’s Conjecture exactly? in 1742, Christian Goldbach, made a following conjecture:

Every even number greater than 4 can be written as the sum of two odd prime numbers.

for example:

8 = 3 + 5, both 3 and 5 are odd prime numbers.
20= 3 + 17 = 17 + 3.

So, To solve this, we have to generate all odd primes that less than a million. from 3 until 1.000.000 . To generate all primes quickly, there exists a method named Sieve of eratosthenes that can generate primes number very quick in O(n log log n). In this post, i assume you already know this algorithm. Maybe in the next post, i’ll post the details of this algorithm.

First, call the sieve function to generate all the primes, then store the prime numbers in another array. Call it array primes, which contain exactly all primes less than a million.

Then simply iterate from the first odd prime, until the last odd prime (remember, all primes are odd except 2). When iterate, you have to give a simple condition to break the iteration if the current prime is more than the input itself. After that, We just subtract the input with the current prime number, then check whether the result is prime number or not by checking the prime numbers array. if the number exists in the prime array, then print the requested output, then simply break from the iteration.

Checking the result whether this result exists in the prime numbers array or not, can be done in O(lg n) complexity with binary search.

Look at the example:
When the input is 8, our first prime number is 3. then subtract 8 with 3 resulting 5. check whether 5 is prime number by find it at the prime array using binary search algorithm.

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<vector>
#include<cstdio>
#define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++)
#define REP(i,n) FOR(i,0,(n)-1)
using namespace std;
vector<int> primes;
void sieve(int n) {
	vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false;
	int i;
	for (i=2; i*i<=n ; i++ ) {
		if (is_prime[i]) {
			if (i!=2) primes.push_back(i);
			for(int j=i*i; j<=n; j+=i) is_prime[j]=false;
		}
	}
	if (i%2==0) i++;
	for(i;i<=n;i+=2) if (is_prime[i]) primes.push_back(i);
}
 
int bs(int left, int right, int x) {
	int mid;
	while (left<=right) {
		mid = (left + right) / 2;
		if (primes[mid] == x) return 1;
		if (x<primes[mid]) {
			right = mid - 1;
		} else {
			left=mid+1;
		}
	}
	return 0;
}
 
int main() {
	sieve(1000002);
	int n;
	while (scanf("%d", &n)!=EOF && n!=0) {
		REP(i,primes.size()) {
			int b = n - primes[i];
			if (bs(i,primes.size()-1,b)) {
				printf("%d = %d + %d\n", n,primes[i],b);
				goto end;
			}
		}
		puts("Goldbach's conjecture is wrong.");
		end:;
	}
	return 0;
}

How about your approach? So, if you have any approach that simplier than this one and you don’t mind to share it with us (me and other readers), just post your approach in the comment.

Thank You..

- Felix J

Read Full Post »