the task is to write a program that adds up all the prime numbers between 1 and 2,000,000
here is my solution
Code:
int main()
{
//declare variables
int i, j, iLimit = 2000000, iMultiples[2000000] = { 0 }; //imultiples is used to mark off multiples of i
unsigned long long int iSum = 0;
//loop from 2 to iLimit
for ( i = 2; i < iLimit; i++ )
{
//check if i is a multiple of a previous itteration of i
if ( iMultiples[i] == 0 )
{
//i is a new prime so add it to the running total isum
iSum += i;
//loop from i to ilimit in all multiples of i
for ( j = i * 2; j < iLimit; j += i )
{
//mark off i * j
iMultiples[j] = 1;
}
}
}
//print the sum of primes from 1 to ilimit to the screen
printf("The sum of primes between 1 and %d is %llu\n", iLimit, iSum);
return 0;
}
this runs in 0.063 seconds
If i change the variable declarations at the top to
Code:
int i, j, iLimit = 2000000;
unsigned long long int iSum = 0;
char iMultiples[2000000] = { '\0' }; //imultiples is used to mark off multiples of i
ie the array is now type char it cuts the run time approximately in half
Looking at the "official" solution they used pointers of type char and calloc'ed the memory and treated it as an array which doesn't appear to be any quicker than using a predefined array of type char so i don't see the point