Run time exceeded in c

Question

I’m doing a program that adds the amount of prime numbers from 1 to 2000,000. When trying to compile, it returns that there was exceeded runtime. I would like to know ways to optimize the time of my program.

    #include <stdio.h>

    int main()
    {
      long long int i = 0, j = 0, count = 0, soma = 0;

      for (j = 1; j <= 2000000; j++, count = 0)
      {

        for (i = 1; i <= 2000000; i++)
        {
          if (j % i == 0)
          {
            count++;
          }
        }

        if (count == 2)
        {
          soma += + j;
        }

      }
      printf("%lld\n", soma);

return 0;
    }

Answer 1

You can use the term sum formula of a P.A. to calculate.

Sn = ((a1+an)*n)/2. No caso Sn = ((1+2000000)*2000000)/2)

Answer 2

Your number primality check is rather inefficient. It doesn’t actually check whether the number is prime.

You can optimize verification by eliminating a good part of the calculations using:

bool ehprimo(int n) {
    int i;
    if (n == 2)
        return true;
    else
        if ((n < 2) || (n % 2 == 0))
            return false;
        else {
            i = 3;
            while ((i <= sqrt(n)) && (n%i != 0))
                i += 2;
            return (i>sqrt(n));
        }
}

The considerations are:

• -1, 0 and 1 are not prime by definition;
• the only prime pair is 2, any multiple of 2 is divisible by 2;
• you just need to check if the odd has no divider between 3 and square root(n).

I think you expressed yourself badly by saying "add up the amount of prime numbers", it seems to me that you just want to calculate the amount and will not add up to anything. Or maybe you mean the sum of the cousins in the interval.