patterncMinor

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

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

cannumberexpressednumberssumcheckprimegiven

Problem

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

Solution

Some general remarks:

Use more horizontal space, for(i=0;i

Use true and false from 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 
#include 

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

 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.

Code Snippets

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

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

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

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

Context

StackExchange Code Review Q#138568, answer score: 4

Revisions (0)

No revisions yet.