Goldbach conjecture exercise (c)

Question

My professor asked me to do a program to test the Goldbach conjecture. I am wondering if I should consider 1 as a prime. This is my code that prints the first combination of prime numbers:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n, i, j, k, l;    
    char prime, prime1;
    do   //check if n is even and greater than 2
    {
        printf("Give me an even natural number greater than 2:\n\n>");
        scanf("%d", &n);
    }
    while (n % 2 != 0 && n >= 2);
    for (i = 1; i < n ; i++) 
    {                   
        prime = 1;     
        for (k = 2; k < i; k++)  
            if (i % k == 0)
                prime = 0;
        if (prime)
        {
            for (j = 1; j < n; j++)
            {
                prime1 = 1;
                for (l = 2; l < j; l++)
                    if (j % l == 0)
                        prime1 = 0;
                if (prime1)
                    if (i + j == n)
                    {
                        printf("\n\n%d and %d are the first two prime numbers that add up to %d.\n", i, j, n);
                        return 0;
                    }
            }
        }
    }
}

I checked the internet and almost everyone says that 1 is not a prime. What should i do? Keep the program as it is or change it so that it won't consider 1 as a prime? And how do I do that? :P

Answer 1

I added an is_prime test. This is easier to read.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
// gcc -o test  gold_test.c -lm

bool is_prime(long n) {
   if (n <= 3) return n > 1;
   if ((n%6 != 1) && (n%6 != 5)) return false;
   long limit = sqrt(n);
   for (long i = 5; i<=limit; i+=6) 
       if (n%i == 0 || n%(i+2) == 0) return false; 
   return true;
}

int main()
{
   long n, i;    
   do   //check if n is even and greater than 2
   {
       printf("Give me an even natural number greater than 2:\n\n>");
       scanf("%ld", &n);
   }
   while (n % 2 != 0 || n < 4);
    
   if (n==4) 
      printf("\n\n%ld and %ld are the first two prime numbers that add up to %ld.\n", 2L, 2L, n);
   else 
      for (i = 3; i <= n/2; i+=2) 
      {                    
         if (is_prime(n-i) && is_prime(i)) {
            printf("\n\n%ld and %ld are the first two prime numbers that add up to %ld.\n", i, n-i, n);
            return 0;
         }
      }
}

Answer 2

you can consider 1 a prime number, as Goldbach did, or not as is the more common usage, it makes almost no difference regarding the conjecture.

Considering 1 as a prime number has this effect:

• there is a solution for 2: 1 + 1.
• the first pair for 4 is 1 + 3 instead of 2 + 2
• the first solution for higher even numbers may involve 1 if the value is a prime number plus one, but no known even number greater than 2 can only be expressed as p + 1.

Note that there are problems in your code:

• you do not check the return value of scanf(), so inputing a string that is not a number will cause undefined behavior (the first time as n is uninitialized) or an infinite loop as n is no longer modified.

• the test while (n % 2 != 0 && n >= 2); is incorrect: it should be:

  while (n <= 2 || n % 2 != 0);
  

• the first loop could iterate half as long with a test i <= n / 2

• the second loop could iterate much less with a test k * k <= i

• you could exit the second loop when you detect that i is not prime

• there is no need for a third loop, you just need to test if n - i is prime

• the same improvements are possible for the second primary test, better move this to a separate function.

• you should have a message and return statement for the remote possibility that you find a counter-example to the Goldbach conjecture ;-)

Here is an improved version:

#include <stdio.h>

#define PRIME_MASK ((1ULL <<  2) | (1ULL <<  3) | (1ULL <<  5) | (1ULL <<  7) |\
                    (1ULL << 11) | (1ULL << 13) | (1ULL << 17) | (1ULL << 19) | \
                    (1ULL << 23) | (1ULL << 29) | (1ULL << 31) | (1ULL << 37) | \
                    (1ULL << 41) | (1ULL << 43) | (1ULL << 47) | (1ULL << 53) | \
                    (1ULL << 59) | (1ULL << 61))

int isprime(unsigned long long n) {
    if (n <= 63)
        return (PRIME_MASK >> n) & 1;
    if (n % 2 == 0)
        return 0;
    for (unsigned long long k = 3; k * k <= n; k += 2) {
        if (n % k == 0)
            return 0;
    }
    return 1;
}

int main(void) {
    unsigned long long n, i;
    int r;

    for (;;) {
        printf("Give me an even natural number greater than 2:\n>");
        r = scanf("%llu", &n);
        if (r == 1) {
            if (n % 2 == 0 && n > 2)
                break;
        } else
        if (r == EOF) {  /* premature end of file */
            return 1;
        } else {
            scanf("%*[^\n]%*c");  /* flush pending line */
        }
    }
#ifdef ONE_IS_PRIME
    i = 1;    /* start this loop at 1 if you want to assume 1 is prime */
#else
    i = (n == 4) ? 2 : 3;
#endif
    for (; i <= n / 2; i += 2) {
        if (isprime(i) && isprime(n - i)) {
            printf("%llu = %llu + %llu\n", n, i, n - i);
            return 0;
        }
    }
    printf("Goldbach was wrong!\n"
           " %llu cannot be written as the sum of two primes\n", n);
    return 0;
}

Answer 3

YOU CAN Consider 1 to be a prime as Goldbach too considered it to be prime in his letter to Leonhard Euler.But that was the time when 1 was considered to be prime.Later it was abandoned and hence this one is Goldbach's third revised conjecture.Also,since today we consider 1 to be neither prime nor composite,even if you don't consider 1 to be a prime number,the conjecture still holds true,is well-verified upto 4*10^18 (re-verified upto 4*10^17).

As far as you deal with the Professor,you should better ask him what does he want.