Check if given number can be expressed as sum of 2 prime numbers

Question

Similar problem: Sum Of Prime

I've done the given problem in roughly \$\mathcal{O}(n\sqrt{n})\$.

How can I improve this algorithm?

#include <stdio.h>
int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}
int main(void) {
    int i, t, prime;
    long long int n, start, end;
    scanf("%d", &t);
    for(i=0;i<t;i++)
    {
        prime = 0;
        scanf("%lld", &n);
        if(n<4)
            printf("No\n");
        else
        {
            if(n%2==0)
                printf("Yes\n");
            else
            {
                start = 2;
                end = n-2;
                while(start<=end)
                {
                    if(isPrime(start) && isPrime(end))
                    {
                        printf("Yes\n");
                        prime = 1;
                        break;
                    }
                    else
                    {
                        start++;
                        end–-;
                    }
                }
                if(prime==0)
                    printf("No\n");
            }
        }
    }
    return 0;
}

Answer 1

Some general remarks:

• Use more horizontal space, for(i=0;i<t;i++) is difficult to read.
• Use true and false from <stdbool.h> for boolean values, not the integers 1 and 0.

• Declare variables at the nearest scope where they are used, e.g. in loops:

  for (long long i = 2; i * i <= n; i++) { ... }
  

• Always use braces { } in if-statements, even if there is only a single statement to be executed in the if- or else-case. Adding the braces easily forgotten if you add more statements later.

• long long int is identical to long long. I prefer the latter, but that is a matter of taste (or your coding style guidelines).

Now to your code:

• The isPrime() functions treats n = 1 as a prime number, which it isn't.
• Separate the computation from the I/O. That makes the code more organized and allows you to add test cases easily.

So the program should look like this:

#include <stdio.h>
#include <stdbool.h>

bool isPrime(long long n) {
    if (n < 2) {
        return false;
    }
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

bool isSumOfTwoPrimes(long long n) {
    // ... check if `n` is the sum of two prime numbers ...
}

int main(void) {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        long long n;
        scanf("%lld", &n);
        if (isSumOfTwoPrimes(n)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

Printing the result can also be done with a single statement:

        puts(isSumOfTwoPrimes(n) ? "Yes" : "No");

You return true for all even numbers, which is correct because Goldbach's conjecture has already been proven for all even numbers in your range 1<=n<=1000000.

For odd numbers, the calculation can be simplified considerably. If n = p + q is odd then p is even and q is odd, or vice versa. Since 2 is the only even prime number, this reduces to check if n - 2 is prime:

bool isSumOfTwoPrimes(long long n) {
    if (n < 4) {
        return false;
    }
    if (n % 2 == 0) {
        return true;
    }
    return isPrime(n - 2);
}

Note another advantage of the separate function: You can "early-return", and that makes the "state variable" int prime from your code obsolete.

If the program is run with a large number of test cases, then a further improvement would be to pre-compute all prime numbers in the given range, for example with the Sieve of Eratosthenes.

Answer 2

int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}

We can do better than this.

#include <stdbool.h>

bool isPrime(long long int n)
{
    if (n <= 1)
    {
        return false;
    }

    if (n % 2 == 0)
    {
        return 2 == n;
    }

    for (long long int i = 3; i * i <= n; i += 2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

At the expense of adding an extra check for 2 outside the loop, the loop can do half the checks by incrementing by 2 instead of 1. This works because no even number greater than 2 is prime.

The return 2 == n check handles the case where it is actually 2. That should return true, as 2 is prime. But all other values that are divisible by 2 should return false.

We can take this another step:

bool isPrime(long long int n)
{
    if (n <= 1)
    {
        return false;
    }

    if (n % 2 == 0)
    {
        return 2 == n;
    }

    if (n % 3 == 0)
    {
        return 3 == n;
    }

    long long int increment = 4;
    for (long long int i = 5; i * i <= n; i += increment)
    {
        if (n % i == 0)
        {
            return false;
        }

        increment = 6 - increment;
    }

    return true;
}

At the expense of another check and some extra logic, eliminate another third of the checks.

The increment variable will alternate between 2 and 4 because 6 - 2 = 4 and 6 - 4 = 2. So i will go

5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, ...

skipping every odd number divisible by three.

Answer 3

Additional remarks:

• I wouldn't use long long for math. There's uintmax_t -- just check whether the number is covered by the Goldbach conjecture or not
• As already hinted: Why don't you use an unsigned type? Because $$ \forall z \in \mathbb{Z}. \forall p,q: (z = p+q \Rightarrow -z = -p -q) $$

So what I've done is:

• added <stdint.h>, <inttypes.h> and <stdbool.h>.
• Replace int with uintmax_t

• Add a macro:

  /* Goldbach conjecture holds true for at least 4*10^18 */
  #define GOLDBACH_MAX 4000000000000000000
  #define MAX_ALLOWED (GOLDBACH_MAX > UINTMAX_MAX) ? UINTMAX_MAX : GOLDBACH_MAX
  

  and then use scanf("%" SCNuMAX, &n);

• added in-program instructions:

  printf("Enter the number of checks to run:\n");
  scanf("%d", &t);
  

• Refactored for-loop. I prefer continue/break over many cascading if-else:

  for(int i=0; i<t; i++) {
      /* [...] input handling elided */
  
      if(n%2==0) {
          printf("Yes\n");
          continue;
      }
  
      uintmax_t start = 2;
      uintmax_t end = n-2;
      bool prime = false;
      while(start<=end) {
          if(isPrime(start) && isPrime(end)) {
              printf("Yes\n");
              prime = true;
              break;
          } else {
              start++;
              end--;
          }
      }
      if(!prime) {
          printf("No\n");
      }
  }
  

• Made input handling more error-proof:

  while (true) {
      int ret = scanf(" %d", &t);
      if (ret == 1) break;
  
      if (ret < 0) perror(__func__);
      fprintf(stderr, "Invalid input, retry\n");
      /* consume all remaining characters in buffer */
      scanf("%*[^0-9\n]");
  }
  

  and

  while (true) {
      printf("Input: ");
      int ret = scanf(" %" SCNuMAX, &n);
      /*
       * we only need to check for smaller-than Goldbach
       * maximum since the other one is already guaranteed by
       * scanf()
       */
      if (ret == 1 && n <= GOLDBACH_MAX) break;
  
      if (ret < 0) perror(__func__);
      fprintf(stderr, "Invalid input, retry\n");
      scanf("%*[^0-9\n]");
  }
  

Putting it all together, this is roughly what I'd have written (so also using my snake_case-style etc. -- this is personal preference)

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdbool.h>
#include <assert.h>

/* Goldbach conjecture holds true for at least 4*10^18 */
#define GOLDBACH_MAX 4000000000000000000
#define MAX_ALLOWED (GOLDBACH_MAX > UINTMAX_MAX) ? UINTMAX_MAX : GOLDBACH_MAX

bool is_prime(uintmax_t n)
{
    assert(n <= GOLDBACH_MAX);

    uintmax_t i;
    for (i=2; i*i<=n; i++) {
        if(n%i == 0) {
            return false;
        }
    }
    return true;
}

int main()
{
    printf("Range: [0,%" PRIuMAX "]\n", MAX_ALLOWED);

    int t;
    printf("Enter the number of checks to run:\n");
    while (true) {
        int ret = scanf(" %d", &t);
        if (ret == 1) break;

        if (ret < 0) perror(__func__);
        fprintf(stderr, "Invalid input, retry\n");
        /* consume all remaining characters in buffer */
        scanf("%*[^0-9\n]");
    }

    for (int i=0; i<t; i++) {
        uintmax_t n;
        while (true) {
            printf("Input: ");
            int ret = scanf(" %" SCNuMAX, &n);
            /*
             * we only need to check for smaller-than Goldbach
             * maximum since the other one is already guaranteed by
             * scanf()
             */
            if (ret == 1 && n <= GOLDBACH_MAX) break;

            if (ret < 0) perror(__func__);
            fprintf(stderr, "Invalid input, retry\n");
            scanf("%*[^0-9\n]");
        }

        if (n < 4) {
            printf("No\n");
            continue;
        }

        if (n%2 == 0) {
            printf("Yes\n");
            continue;
        }

        uintmax_t start = 2;
        uintmax_t end = n-2;
        bool prime = false;
        while (start <= end) {
            if (is_prime(start) && is_prime(end)) {
                printf("Yes\n");
                prime = true;
                break;
            } else {
                start++;
                end--;
            }
        }
        if (!prime) {
            printf("No\n");
        }
    }

    return 0;
}