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

• Martin R: You return "Yes" for every even number, so you take the Goldbach conjecture for granted. If an odd number is the number of two primes then one of them must be 2 (the only even prime number).
• Shreyas HM: yes I used the Goldbach conjecture because the original problem had the constraints 1<=n<=1000000. Since Goldbach conjecture holds good for even numbers up to 4 x 10^18, I used it. Could you explain what do you mean by "if an odd number is the number of two primes"?
• Martin R: If n = p + q is odd then p is even and q is odd, or vice versa. There is only one even prime number. – Btw, if this is from a programming challenge then you might add a link to the problem.
• Shreyas HM: So, do you mean to say that if an odd number can be expressed as the sum of 2 primes, then one of them has to be 2. Which means I only need to check if n-2 is prime?

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.

• Shreyas HM: So, for the program you've given now (putting aside the further improvement with the Sieve), the time complexity would be O(√n), correct?
• Martin R: @ShreyasHM: Yes, that should be correct.
• Shreyas HM: Awesome! :) really appreciate the explanation and the valuable insights. I'll make sure to follow the advice you've given too :) Thanks for your time :)
• Martin R: @ShreyasHM: You are welcome (and welcome on Code Review)! – I have added some more notes ...

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

• Chris: I would further factor your code to repeatedly prompt for an integer out into a separate get_int (naming left to personal taste) function.

Answer 4

How can I improve this algorithm?

Avoid overflow

i*i risks signed integer overflow when n is a large prime. Consider a prime just less than LLONG_MAX.

It might take some time to increment up to about to the sqrt(LLONG_MAX) neighborhood, yet undefined behavior (UB), such as an infinite loop, is possible.

Use i <= n/i instead of i*i <= n. A good compiler will see n/i and nearby n%i and then emit efficient code doing both for the time cost of one. Alternative: research lldiv().

isPrime(negative_numbers) errantly returns 1

Also errant for isPrime(0), isPrime(1).

Alternative

int isPrime(long long n) {
 // If even ... (simple bit test)
 if (n%2 == 0) {
 return n == 2;
 }
 // Test odd divisors.
 for (long long i = 3; i <= n/i; i += 2) {
 if (n%i == 0) {
 return 0;
 }
 }
 return n > 1;
}

Consider using unsigned types

Maybe also a bool return.

bool isPrime(unsigned long long n) {

---

Might be able to get by with for (long /* long long */ i = 3; i <= n/i; i += 2) {. Will look into it - Edge cases you know ...

Answer 5

For time complexity, you can easily improve it to O(n log log n) preprocessing by finding all primes below n using the Sieve of Eratosthenes. The Prime Number Theorem tells us there are about O(n / log n) primes, so each query can be answered in that time via 2-sum (throw them into a hash set and check if n - p is in the set in linear to the list size time)