How do I perform “Millions of Calculations?”

Question

My code is pasted below.When I run this program,it keeps on calculating.I am using the old Turbo C++ compiler.How much time should such a program take to execute?I waited about 5 minutes but there wasn't any output.

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

Answer 1

You aren't doing millions of calculations, you are doing trillions of them.

IsPrime will run in O(n) time, that is it will perform 2 million instructions just to determine that single number. Doing that sort of thing two millions time will take way too long.

To do this you really want to use something like: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, which can much more efficently determine all of the prime numbers in a particular range.

Answer 2

How much time should such a program take to execute?

That depends completely on your platform. I suspect since you're performing ~(two million)^2 operations (~four trillion) calculations, an awful long time.

There are much better ways to perform what you're doing -- for example to check prime you only need to check to the square root of the number, not all the way up to the number itself. Not to mention there is probably a dynamic programming solution which can do it much much faster than that.

Answer 3

As others have said, it will take a long time. One alternate and interesting approach is the Sieve of Eratosthenes. You can read about it at:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Basically you initialize an array with the numbers 2...2 million. The lowest number not yet processed is prime. Then, you remove all multiples of this number from the array and continue. It will run much faster than what you have.

Answer 4

Off-beat answer

gotoxy(25,25);

Do you run your program in text mode? If the text screen is only 80 x 25, and if the 25th line is occluded by some other things, then chances are you won't see any change in the text screen.

Answer 5

As others have said: check the limits of your implementation

If TurboC++ has <limits.h>, those implementation limits have a corresponding macro defined in that header

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

If that fails you need to "calculate" the limits yourself. I'm switching to unsigned because there's no overflow problem with them, and I only need to "calculate" the upper limit (the lower limit is 0)

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}

---

On my system, the 1st program outputs

int goes from -2147483648 to 2147483647.
long goes from -9223372036854775808 to 9223372036854775807.

and the 2nd program outputs

unsigned ints go all the way to 4294967295
unsigned longs go all the way to 18446744073709551615

Answer 6

Still no comment/answer about the constant except an "Epic"...

#define TWO_MILLION 2*1000*1000

This is bad. When you change the value later, you either have a name-content-mismatch:

#define TWO_MILLION 5*1000*1000

or you rename it to

#define FIVE_MILLION 5*1000*1000

and need to change it everywhere you've used it. Don't name your constants after the content, this just turns your magic numbers into magic names. Name them after their meaning, e.g. MAX_NUMBER UPPER_LIMIT RANGE_TO_TEST or whatever fits best.

Answer 7

you can use sieve methods to do this as well that aren't much more complicated than what you are using. The idea is to pick the first n consecutive prime numbers and use them to construct a sieve. I discuss it (with proofs) in my answer to another question and Sheldon L. Cooper provides an implementation in his. I don't think he got enough upvotes for doing so (I already got 'nice answer', so maybe you could help him out on that.

so after you calculate the sieve numbers, you only need to test for divisibility by numbers that line up with the sieve and are smaller than the square root of n.

Answer 8

This could take a very long time to run.

Add this to see your progress (though it will take even longer):

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

Edit

As others are pointing out, this is the slowest way to count primes. Perhaps the purpose of your assignment is to get you to look up (and implement) faster ones?

Answer 9

Your program results in integer overflow, you could use long long to fix it.

Also, your algorithm for checking if a number is prime is not very good. Another way that is just as easy is to test the numbers 2 to the square root of the number. You only have to check up to the square root of the number to determine if it is prime.

Answer 10

A simple change would show you how fast your program is running, and how much work it has to do. It is easy to print out your status around every 100 iterations. (Or you could set it to 1000, or 10000 iterations.)

---

Recognize that you could DOUBLE the speed of your loop in IsPrime.
After you check 2, you only need to check odd numbers, and could advance with i+=2 instead of i++.

If you're concerned about speed, why are you spending so much time checking even numbers? (note that once you start doing only odd-numbers, you also need to change the output test to be a odd number)

You can DOUBLE the speed of the loop in main as well by also avoiding even numbers there. (again, you have to special-case 2, then use i+=2, starting at 3 to get 3, 5, 7, 9....)

By making the loop in IsPrime run twice as fast, and making the loop in main run twice as fast, this should make your program go 4X faster. (if it would've taken an hour before, now it'll be 15 minutes.)

---

The other big speed improvement you could make is only running the loop to sqrt(num), instead of num

Since I hate bringing in floating point functions, such as sqrt, I instead suggest a close approximation that will stop within 100 iterations of passing the sqrt boundary, and also show status updates regularly.

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

---

P.S. I put this code into a C# project (minor porting). Granted, this was now running on a 64-bit OS, with a better compiler and 2.8GHz CPU.
It ran in less than 20 seconds.