Check if given number can be expressed as sum of 2 prime numbers 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 &lt;stdio.h&gt;
int isPrime(long long int n)
{
    long long int i;
    for(i=2;i*i&lt;=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", &amp;t);
    for(i=0;i&lt;t;i++)
    {
        prime = 0;
        scanf("%lld", &amp;n);
        if(n&lt;4)
            printf("No\n");
        else
        {
            if(n%2==0)
                printf("Yes\n");
            else
            {
                start = 2;
                end = n-2;
                while(start&lt;=end)
                {
                    if(isPrime(start) &amp;&amp; isPrime(end))
                    {
                        printf("Yes\n");
                        prime = 1;
                        break;
                    }
                    else
                    {
                        start++;
                        end–-;
                    }
                }
                if(prime==0)
                    printf("No\n");
            }
        }
    }
    return 0;
}
Some general remarks:


Use more horizontal space, for(i=0;i&lt;t;i++) is difficult to read.
Use true and false from &lt;stdbool.h&gt; 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 &lt;= 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 &lt;stdio.h&gt;
#include &lt;stdbool.h&gt;

bool isPrime(long long n) {
    if (n &lt; 2) {
        return false;
    }
    for (long long i = 2; i * i &lt;= 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", &amp;t);
    for (int i = 0; i &lt; t; i++) {
        long long n;
        scanf("%lld", &amp;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&lt;=n&lt;=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 &lt; 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.