HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Sum of all primes under 2 million

Submitted by: @import:stackexchange-codereview··
0
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:

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