8
\$\begingroup\$

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?

\$\endgroup\$

migrated from stackoverflow.com Dec 26 '11 at 16:07

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ Why are you using a long double in the outer loop? Will you show all of your code? \$\endgroup\$ – Omnifarious Dec 26 '11 at 5:35
  • 1
    \$\begingroup\$ You have searched ... right? Various trivial optimizations are discussed at great length on the inter-webs. Many numbers can be trivial skipped. (All evens > 2, all numbers ending in 0 or 5 > 5, every second "advance 2" > 3, etc.) Also, consider i < sqrt(number), where sqrt(number) is a constant for the function. \$\endgroup\$ – pst Dec 26 '11 at 5:43
  • 1
    \$\begingroup\$ Sieve of Eratosthenes \$\endgroup\$ – Martin York Dec 26 '11 at 17:43
14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Please clarify your answer. What is a sieve? Why should he not multiply by i? \$\endgroup\$ – Dimme Dec 26 '11 at 5:35
  • \$\begingroup\$ Also, do not test against any even numbers except 2! \$\endgroup\$ – bobbymcr Dec 26 '11 at 5:36
  • 5
    \$\begingroup\$ A sieve is a means of finding all primes less than a given number. He shouldn't multiply i by itself every time in the loop because it's a multiplication every single pass in the loop and it serves no purpose. He should just calculate what number he wants to loop to once rather than doing it each pass in the loop. \$\endgroup\$ – David Schwartz Dec 26 '11 at 5:37
  • \$\begingroup\$ Eratosthenes sieve would be the more common name, except for those who are familiar with prime problems \$\endgroup\$ – prusswan Dec 26 '11 at 5:40
  • 1
    \$\begingroup\$ The other well-known optimization for "IsPrime" is that you need not check for any factoring for values above sqrt(number) if you checked all the vales less that sqrt(number). (And for the love of Bob, don't inline sqrt(number) into your loop - calculate it once! \$\endgroup\$ – selbie Dec 26 '11 at 5:43
7
\$\begingroup\$

To enumerate all prime number below a limit you could use Sieve of Eratosthenes as mentioned by @David Schwartz in the comment:

#include <cmath>
#include <iostream>
#include <vector>
#include <stdint.h>

namespace {
  // yield all prime numbers less than limit.
  template<class UnaryFunction>
  void primesupto(int limit, UnaryFunction yield)
  {
    std::vector<bool> is_prime(limit, true);

    const int sqrt_limit = std::sqrt(limit);
    for (int n = 2; n <= sqrt_limit; ++n)
      if (is_prime[n]) {
        yield(n);    
        for (unsigned k = n*n, ulim = limit; k < ulim; k += n)
          //NOTE: "unsigned" is used to avoid an overflow in `k+=n`
          //for `limit` near INT_MAX
          is_prime[k] = false;
      }

    for (int n = sqrt_limit + 1; n < limit; ++n)
      if (is_prime[n])
        yield(n);
  }
}

int main() {
  uintmax_t sum = 0;
  primesupto(2000000, [&sum] (int prime) { sum += prime; });
  std::cout << sum << std::endl;
}

Demo

$ g++ -std=c++0x sum-primes.cc -o sum-primes && ./sum-primes
142913828922
\$\endgroup\$
5
\$\begingroup\$

I have done that before. The point is that you don't have to divide your number by all odd numbers smaller than it, but by all PRIME numbers smaller than it.

So, pass the list of the prime numbers you had found to the function and divide your new number by each them.

\$\endgroup\$
3
\$\begingroup\$

Your IsPrime function looks OK. This won't help it's speed very much, but it will a little...

bool isPrime(unsigned int number) {
   if (number <= 1) {
      return false;
   } else if (number % 2 == 0) {
      return number == 2;
   } else {
      for (unsigned int i = 3; true; i += 2) {
         const unsigned int remainder = number % i;
         const unsigned int quotient  = number / i;
         if (remainder == 0) {
            return false;
         } else if (quotient < i) {
            return true;
         }
      }
   }
}

This is only slightly faster because some processors have a combined 'find the remainder and quotient' instruction that this leverages. It also avoids testing even numbers. If your number is not divisible by 2, it won't be divisible by any other even number other, since all even numbers can also be divided by 2.

Also, make sure you have compiler optimizations turned on.

\$\endgroup\$
2
\$\begingroup\$

For every prime number n>=5, n mod 6 returns 1 or n mod 6 returns 5. If you check these candidates for primeness by seeing if any prime number that is less than or equal to sqrt(n) divides a candidate could help eliminate many checks. When you do find a prime number, you could add to a list or, just add up to get the sum. The thing about this method is, it helps eliminate many checks that would simply return composite instead of prime, which is what you are looking for.

\$\endgroup\$
0
\$\begingroup\$

As others have pointed out, you can cut your work in half by avoiding even numbers. However, avoiding even numbers after 2 is just the first part of using a sieve: if you filter by every prime number found up to the square root of a particular number that you want to test, you can check by only those numbers.

Here is some java-like psuedocode to illustrate what I'm saying:

public List findPrime(int upperLimit){
    List primes = new List();
    primes.add(2);
    for(int i=3;i<upperLimit;i++){
        boolean primeFlag = true;
        for(test in primes){
            if(test > sqrt(i)
                break;
            if(i % test == 0){
                primeFlag = false; break;
            }
        }
        if(primeFlag) primes.add(i);
     }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy