如何优化这些C for循环？

Question

我选择在C中执行这些Project Euler问题，因为我的印象是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

随着分支预测不按需要：

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; 
      } 
     } 

这完成：

寻找在problem7例如，这可以通过使用 if语句加快在0.88secs而不是原来的9.5secs - 比那个更改快了10多倍

优化的解释和合理的等价：

的变化作出了从原线：

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

首先改变的是它的等效：

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

注意如何factorCounter只能递增，并且在循环之后，任何超过1的值都被丢弃，因为(factorCounter == 1)将是错误的，所以一旦它大于1，就没有理由继续循环。还要注意的是，当(j%k==0)所以测试为factorCounter > 1应的，如果检查中出现只能改变factorCounter值，代码是现在：

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

和退出循环早期是什么让性能增益

Answer 2

我想我会做出这个答案。你的程序很慢，因为你的循环设计不好，嵌套不好。我不打算做一个复杂性分析，但是你在O（N^x）范围内的某个地方，其中x> 4（从我所知道的）。

这只是不好的编程，它与循环优化没有多大关系。你需要使用像Sieve of Eratosthenes这样的东西来解决Eu​​ler 7.我不会在这里给你解决方案，就像Wiki文章那样，解决这个问题相当微不足道。

Answer 3

C很快。高级语言也可以很快。但即使是最好的编译器也无法优化你所做的额外操作！减少问题7算法中操作次数的一种简单方法是，如果factorCounter变得大于1，则打破最深的循环。很抱歉将它分解给你，但是：它不是编译器，它是算法！

Answer 4

几乎立即执行更直接的问题。你并不需要那么多的优化。使用布尔数值

#include <iostream> 
#include <cmath> 

using namespace std; 

bool isPrime(int j) 
{ 
    for(int fac = 2; fac < sqrt(j)+0.5; ++fac) 
     if(j%fac == 0) 
      return false; 

    return true; 
} 

int main() 
{ 
    int primesFound = 1; // 2 is prime 
    int possiblePrime = 1; 

    while(primesFound != 10001) 
    { 
     possiblePrime += 2; 
     if(isPrime(possiblePrime)) 
      ++primesFound; 
    } 

    cout << possiblePrime << endl; 
}