3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Somehow all the double quotes in your code became typographical quotation marks “...”. \$\endgroup\$ – Martin R Aug 12 '16 at 18:41
  • \$\begingroup\$ @MartinR yes lol...no idea how that happened \$\endgroup\$ – Shreyas HM Aug 12 '16 at 18:54
  • \$\begingroup\$ 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). \$\endgroup\$ – Martin R Aug 12 '16 at 19:00
  • \$\begingroup\$ 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"? \$\endgroup\$ – Shreyas HM Aug 12 '16 at 19:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin R Aug 12 '16 at 19:15
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ So, for the program you've given now (putting aside the further improvement with the Sieve), the time complexity would be O(√n), correct? \$\endgroup\$ – Shreyas HM Aug 12 '16 at 19:46
  • \$\begingroup\$ @ShreyasHM: Yes, that should be correct. \$\endgroup\$ – Martin R Aug 12 '16 at 19:50
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Shreyas HM Aug 12 '16 at 19:52
  • \$\begingroup\$ @ShreyasHM: You are welcome (and welcome on Code Review)! – I have added some more notes ... \$\endgroup\$ – Martin R Aug 12 '16 at 20:23
1
\$\begingroup\$
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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.