patterncppModerate
Sum of all primes under 2 million
Viewed 0 times
millionprimesallundersum
Problem
I have this assignment to write the optimized space and time code for finding the sum of all primes under 2 million. I'm using the following function to check if each number is prime:
And running a
int IsPrime(unsigned int number) {
if (number <= 1) return 0;
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}And running a
for loop from 1 to 2 million using a long double, and checking each number if it is prime and then adding it. Is there a more optimized method to do this?Solution
There are dozens of possible optimizations. The most obvious -- why are you multiplying
And why
Also, since you need to find all the primes up to a given point, you should be using a sieve rather than testing each number.
i by itself every pass in the loop?! Just calculate the loop cut off once.And why
i++?! After you test 2, there's no reason to test 4, 6, or 8. You can test 2, and then start from 3 adding 2 each time instead of one.Also, since you need to find all the primes up to a given point, you should be using a sieve rather than testing each number.
Context
StackExchange Code Review Q#7167, answer score: 15
Revisions (0)
No revisions yet.