c - 如何优化我的代码，计算小于 200 万的所有总和

Question

我已经从 Project Euler 尝试过这个问题我需要计算所有质数的总和，直到 200 万。

这是我想出的解决方案-

#include <stdio.h>

int main() {
    long sum = 5;  // Already counting 2 and 3 in my sum.
    int i = 5;     // Checking from 5 
    int count =  0;
    while (i <= 2000000) {
        count = 0;
        for (int j = 3; j <= i / 2; j += 2) {
            // Checking if i (starting from 5) is divisible from 3 
            if (i % j == 0) {   // to i/2 and only checking for odd values of j
                count = 1;
            }
        }
        if (count == 0) {
            sum += i;
        }
        i += 2;
    }
    printf("%ld ", sum);
}

运行大约需要 480 秒，我想知道是否有更好的解决方案或提示来改进我的程序。

________________________________________________________
Executed in  480.95 secs    fish           external
   usr time  478.54 secs    0.23 millis  478.54 secs
   sys time    1.28 secs    6.78 millis    1.28 secs

Answer 1

通过两个小的修改，您的代码变得更快:

#include <stdio.h>
#include <math.h>

int main() {
  long long sum = 5;    // we need long long, long might not be enough
                        // depending on your platform
  int i = 5;
  int count = 0;
  while (i <= 2000000) {
    count = 0;

    int limit = sqrt(i);                  // determine upper limit once and for all
    for (int j = 3; j <= limit; j += 2) { // use upper limit sqrt(i) instead if i/2
        if (i % j == 0) {
          count = 1;
          break;                          // break out from loop as soon 
                                          // as number is not prime
        }
    }
    if (count == 0) {
      sum += i;
    }
    i += 2;
  }
  printf("%lld ", sum);                   // we need %lld for long long
}

所有解释都在评论中。

但肯定有更好甚至更快的方法来做到这一点。

我在我 10 岁的 MacPro 上运行了这个程序，对于 2000 万 的第一个质数，它花费了大约 30 秒。