c - 如何优化这些 C for 循环？

Question

我选择做这些 Project Euler C 中的问题，因为我的印象是 C 很快，但事实并非如此。以下两个循环都非常慢:

int problem_7 () { 
  int n = 0;
  for (int i = 1; i <= 10001; i++) {
      for (int j = (i==1)?1:n+1; j > 0; j++) {
          int factorCounter = 0;
          for (int k = 1; k <= j/2; k++)
              factorCounter += (j % k == 0);
          if (factorCounter == 1) {
              n = j;
              break;
          }
      }
  }
  return n;
}


long long int problem_10 () {
  long long int sum = 0;
  for (int i = 2; i < 2000000; i++) {
      int factorCount = 0;
      for (int j = 1; j <= i/2; j++) {
          factorCount += (i % j == 0);
          sum += i*(j == i/2 && factorCount == 1);
      }
  }

  return sum; 
} 

有什么方法可以使这些循环运行得更快？他们做他们应该做的事，但他们每个人都需要大约 5 分钟的时间来执行。

Answer 1

使用 bool 数值的分支预测不是必需的:

以问题 7 为例，这可以通过使用 if 语句来加速:

  int n = 0;
  for (int i = 1; i <= 10001; i++) {
      for (int j = (i==1)?1:n+1; j > 0; j++) {
          int factorCounter = 0;
          for (int k = 1; k <= j/2; k++)
          {
              if (j%k==0)                 // code is changed HERE
              {
                factorCounter ++;
                if (factorCounter > 1)
                {
                      break;
                }
              }                          // code change ends here
          }
          if (factorCounter == 1) {
              n = j;
              break;
          }
      }

与原来的 9.5 秒 相比，这在 0.88 秒 内完成——比那一次更改快 10 多倍

优化说明和等价原理:

所做的更改来自原始行:

factorCounter += (j % k == 0);

首先把它改成它的等价物:

if (j%k==0)
{
    factorCounter ++;
}

注意 factorCounter 只能递增，并且在循环后任何超过 1 的值都会被丢弃，因为 (factorCounter == 1) 将为假，所以一旦它更大比 1，没有理由继续循环。另请注意，factorCounter 的值只能在 (j%k==0) 时更改，因此应该进行 factorCounter > 1 的测试在 if 检查中，代码现在是:

if (j%k==0)
{
      factorCounter ++;
      if (factorCounter > 1)
      {
         break;   // We stop the loop much earlier HERE
      }
}

提早退出循环可以提高性能