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

}

Comments

[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 ?