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