Hakan Torun

Posted on

# Goldbach Conjecture And A Simple Approach in C

The Goldbach conjecture is the claim that every double integer greater than 2 can be written as the sum of two prime numbers. It is one of the biggest mathematical problems that cannot be proved.

In the original Goldbach hypothesis, Goldbach claims that every integer greater than 2 can be written as the sum of 3 prime numbers. This claim was put forward with the assumption that the number 1 is the prime number. But now 1 is not a prime number. This claim, which we treat as a Goldbach conjecture, consists of Euler's correction that βevery double integer greater than 2 can be written as the sum of two prime numbers".

For example; 4,6,8,10 and 12 numbers can be write as 2 prime number pairs.

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5

This example C code, which allows a double integer greater than 2 to be written as two prime numbers. E.g. 124620;

124620 = 19 + 124601

``````
#include <stdio.h>

//Function declerations
int is_prime(int n);
void goldbach(int g);

int main(){
int number = 0;
while(1){
printf("Enter even number:");
scanf("%d",&number);
if(number>2 && number%2==0){
goldbach(number);
}
else{
printf("Incorrect number!\n");
}
printf("\n");
}
return 0;
}

//Check is prime number?
int is_prime(int n){
int flag = 1;
for (int j = 2; j < n/2; j++)
{
if((n%j) == 0){
return flag-1;
}
}
return flag;
}

//Goldbach solution of a double integer greater than 2
void goldbach(int g){
int i = 2;

for (int j = g-i; j > 2; j--)
{
if(is_prime(i) == 1 && is_prime(j) == 1)
{
printf("%d = %d + %d\n",g,i,j);
break;
}
i++;
}
}

``````

All two prime pairs. E.g. 16;

16 = 3 + 13
16 = 5 + 11
16 = 11 + 5
16 = 13 + 3

``````#include <stdio.h>

//Buffer for primes
int primes[100000] = {2};
int j = 0;

//Function declerations
int is_prime(int n);
void goldbach(int g);

int main(){
int number = 0;
while(1){
printf("Enter even number:");
scanf("%d",&number);
if(number>2 && number%2==0){
goldbach(number);
}
else{
printf("Incorrect number!\n");
}
printf("\n");
}
return 0;
}

//Check is prime?
int is_prime(int n){
int flag = 1;
for (int j = 2; j < n/2; j++)
{
if((n%j) == 0){
return flag-1;
}
}
return flag;
}

//Goldbach solutions of a double integer greater than 2.
void goldbach(int g){
int flag = 0;

if(primes[j]<g){
for (int i = primes[j]+1; i < g; i++)
{
if(is_prime(i) == 1){
j++;
primes[j] = i;
}
}
}

for (int i = 0; i < j; i++)
{
for (int k = 0; k < j; k++)
{
if(primes[i] + primes[k] == g){
printf("%d = %d + %d\n",g,primes[i],primes[k]);
break;
}
}
}

}

``````

Frank Puffer

Your code probably does its job (haven't tried it) but I suggest some refactorings:

• You can easily avoid the global variables `primes` and `j` by declaring them inside `main`. Yes, you will have to pass additional arguments to `goldbach` but that's fine.

• It is hard to understand what the meaning of `j` is. You should use a more expressive name like `last_prime_index`.

• In `is_prime` you declare another variable `j` which shadows the global `j`. This can easily cause errors.

• In `is_prime`, instead of `j < n/2`, you should check if `j <= sqrt(n)`. This will make your code much more performant for larger numbers.

• In `is_prime`, instead of declaring a `flag`, you could simply return 0 or 1.

• In `goldbach`, the `flag` variable is not used.

• The `goldbach` function does two different things, calculation and output. It could be split into two separate functions.

• You should check if `j < 100000` before incrementing it.

txz32102

# include

int is_prime(int);
void f(int);
int main()
{
int n;
scanf("%d",&n);
f(n);
}
int is_prime(int a)
{
int i;
for(i=2;i*i<=a;i++)
{
if(a%i==0)
return(0);
if(i*i>a)
return(1);
}
}
void f(int n)
{
int a,b,i,j;
for(i=2;i<=n;i++)
{
a=i;
if(is_prime(a))
{
b=n-a;
}
if(is_prime(b))
{
printf("%d=%d+%d",n,a,b);
break;
}
}
}

txz32102

this code work with the number 4 and 6

Paulinho

Why the first code doesn't work with the number 4 ?