更多关于C版本的数字和解释。显然这么多年来没人这么做过。记得给这个答案点赞，这样它就可以放在最上面，让每个人都能看到和学习。

第一步:作者程序的基准

笔记本电脑的规格:

CPU i3 M380 (931 MHz -最大省电模式) 4 gb内存 Win7 64位 微软Visual Studio 2012终极版 Cygwin与gcc 4.9.3 Python 2.7.10

命令:

compiling on VS x64 command prompt > `for /f %f in ('dir /b *.c') do cl /O2 /Ot /Ox %f -o %f_x64_vs2012.exe`
compiling on cygwin with gcc x64   > `for f in ./*.c; do gcc -m64 -O3 $f -o ${f}_x64_gcc.exe ; done`
time (unix tools) using cygwin > `for f in ./*.exe; do  echo "----------"; echo $f ; time $f ; done`

.

----------
$ time python ./original.py

real    2m17.748s
user    2m15.783s
sys     0m0.093s
----------
$ time ./original_x86_vs2012.exe

real    0m8.377s
user    0m0.015s
sys     0m0.000s
----------
$ time ./original_x64_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./original_x64_gcc.exe

real    0m20.951s
user    0m20.732s
sys     0m0.030s

文件名为:integertype_architecture_compiler.exe

Integertype目前与原始程序相同(稍后详细介绍) 架构是x86或x64，取决于编译器设置 编译器是GCC或vs2012

第二步:调查、改进和再次基准

VS比gcc快250%。这两个编译器应该给出类似的速度。显然，代码或编译器选项有问题。让我们调查!

首先要注意的是整数类型。转换可能很昂贵，一致性对于更好的代码生成和优化很重要。所有整数都应该是相同的类型。

它现在是int和long的混合体。我们要改进这一点。使用哪种类型?最快的。必须对它们进行基准测试!

----------
$ time ./int_x86_vs2012.exe

real    0m8.440s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int_x64_vs2012.exe

real    0m8.408s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int32_x86_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int32_x64_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x86_vs2012.exe

real    0m18.112s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x64_vs2012.exe

real    0m18.611s
user    0m0.000s
sys     0m0.015s
----------
$ time ./long_x86_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.000s
----------
$ time ./long_x64_vs2012.exe

real    0m8.440s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x86_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x64_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.015s
----------
$ time ./uint64_x86_vs2012.exe

real    0m15.428s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint64_x64_vs2012.exe

real    0m15.725s
user    0m0.015s
sys     0m0.015s
----------
$ time ./int_x64_gcc.exe

real    0m8.531s
user    0m8.329s
sys     0m0.015s
----------
$ time ./int32_x64_gcc.exe

real    0m8.471s
user    0m8.345s
sys     0m0.000s
----------
$ time ./int64_x64_gcc.exe

real    0m20.264s
user    0m20.186s
sys     0m0.015s
----------
$ time ./long_x64_gcc.exe

real    0m20.935s
user    0m20.809s
sys     0m0.015s
----------
$ time ./uint32_x64_gcc.exe

real    0m8.393s
user    0m8.346s
sys     0m0.015s
----------
$ time ./uint64_x64_gcc.exe

real    0m16.973s
user    0m16.879s
sys     0m0.030s

整数类型是int long int32_t uint32_t int64_t和uint64_t from #include <stdint.h>

C语言中有很多整数类型，还有一些带符号/无符号的可以使用，还有编译为x86或x64的选择(不要与实际的整数大小混淆)。要编译和运行^^的版本太多了

第三步:理解数字

最终结论:

32位整数比64位整数快200% 无符号64位整数比有符号64位快25%(不幸的是，我对此没有解释)

陷阱问题:“C语言中int和long的大小是多少?” 正确答案是:C中int和long的大小没有很好的定义!

来自C规范:

Int至少是32位 Long至少是int型

从gcc手册页(-m32和-m64标志):

32位环境将int、long和指针设置为32位，并生成可在任何i386系统上运行的代码。 64位环境将int设置为32位，long设置为64位，指针设置为64位，并为AMD的x86-64架构生成代码。

来自MSDN文档(数据类型范围)https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx:

Int, 4字节，也是有符号的 Long, 4字节，也称为Long int和带符号的Long int

总结一下:吸取的教训

32位整数比64位整数快。 标准整数类型在C和c++中都没有很好地定义，它们取决于编译器和体系结构。当你需要一致性和可预测性时，使用uint32_t整数族从#include <stdint.h>。 速度问题解决。所有其他语言都落后百分之百，C和c++又赢了!他们总是这样。接下来的改进将是使用OpenMP:D进行多线程处理

通过使用Haskell包中的一些函数，可以大大加快Haskell实现的速度。 在这种情况下，我使用了质数，它只是安装了'cabal安装质数';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

计时:

您的原始程序:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

改进的实现

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

正如你所看到的，在同一台机器上，这台机器运行38毫秒，而你的机器运行16秒:)

编译命令:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe

c++ 11， < 20ms for me -在这里运行它

我理解您想要一些技巧来帮助提高您的语言特定知识，但由于这里已经很好地介绍了这一点，我想我应该为那些可能看过您的问题的mathematica注释等并想知道为什么这段代码如此之慢的人添加一些上下文。

这个答案主要是为了提供上下文，希望能够帮助人们更容易地评估您的问题/其他答案中的代码。

这段代码只使用了一些(丑陋的)优化，与所使用的语言无关，基于:

每个三角数的形式都是n(n+1)/2 N和N +1是互质 除数的数量是一个乘法函数

#include <iostream>
#include <cmath>
#include <tuple>
#include <chrono>

using namespace std;

// Calculates the divisors of an integer by determining its prime factorisation.

int get_divisors(long long n)
{
    int divisors_count = 1;

    for(long long i = 2;
        i <= sqrt(n);
        /* empty */)
    {
        int divisions = 0;
        while(n % i == 0)
        {
            n /= i;
            divisions++;
        }

        divisors_count *= (divisions + 1);

        //here, we try to iterate more efficiently by skipping
        //obvious non-primes like 4, 6, etc
        if(i == 2)
            i++;
        else
            i += 2;
    }

    if(n != 1) //n is a prime
        return divisors_count * 2;
    else
        return divisors_count;
}

long long euler12()
{
    //n and n + 1
    long long n, n_p_1;

    n = 1; n_p_1 = 2;

    // divisors_x will store either the divisors of x or x/2
    // (the later iff x is divisible by two)
    long long divisors_n = 1;
    long long divisors_n_p_1 = 2;

    for(;;)
    {
        /* This loop has been unwound, so two iterations are completed at a time
         * n and n + 1 have no prime factors in common and therefore we can
         * calculate their divisors separately
         */

        long long total_divisors;                 //the divisors of the triangle number
                                                  // n(n+1)/2

        //the first (unwound) iteration

        divisors_n_p_1 = get_divisors(n_p_1 / 2); //here n+1 is even and we

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1);   //n_p_1 is now odd!

        //now the second (unwound) iteration

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1 / 2);   //n_p_1 is now even!
    }

    return (n * n_p_1) / 2;
}

int main()
{
    for(int i = 0; i < 1000; i++)
    {
        using namespace std::chrono;
        auto start = high_resolution_clock::now();
        auto result = euler12();
        auto end = high_resolution_clock::now();

        double time_elapsed = duration_cast<milliseconds>(end - start).count();

        cout << result << " " << time_elapsed << '\n';
    }
    return 0;
}

我的台式机平均花费19毫秒，笔记本电脑平均花费80毫秒，这与我在这里看到的大多数其他代码相差甚远。毫无疑问，还有许多优化方法可用。

尝试:

package main

import "fmt"
import "math"

func main() {
    var n, m, c int
    for i := 1; ; i++ {
        n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
        for f := 1; f < m; f++ {
            if n % f == 0 { c++ }
    }
    c *= 2
    if m * m == n { c ++ }
    if c > 1001 {
        fmt.Println(n)
        break
        }
    }
}

我得到:

原始版本:9.1690 100% Go: 8.2520 111%

但使用:

package main

import (
    "math"
    "fmt"
 )

// Sieve of Eratosthenes
func PrimesBelow(limit int) []int {
    switch {
        case limit < 2:
            return []int{}
        case limit == 2:
            return []int{2}
    }
    sievebound := (limit - 1) / 2
    sieve := make([]bool, sievebound+1)
    crosslimit := int(math.Sqrt(float64(limit))-1) / 2
    for i := 1; i <= crosslimit; i++ {
        if !sieve[i] {
            for j := 2 * i * (i + 1); j <= sievebound; j += 2*i + 1 {
                sieve[j] = true
            }
        }
    }
    plimit := int(1.3*float64(limit)) / int(math.Log(float64(limit)))
    primes := make([]int, plimit)
    p := 1
    primes[0] = 2
    for i := 1; i <= sievebound; i++ {
        if !sieve[i] {
            primes[p] = 2*i + 1
            p++
            if p >= plimit {
                break
            }
        }
    }
    last := len(primes) - 1
    for i := last; i > 0; i-- {
        if primes[i] != 0 {
            break
        }
        last = i
    }
    return primes[0:last]
}



func main() {
    fmt.Println(p12())
}
// Requires PrimesBelow from utils.go
func p12() int {
    n, dn, cnt := 3, 2, 0
    primearray := PrimesBelow(1000000)
    for cnt <= 1001 {
        n++
        n1 := n
        if n1%2 == 0 {
            n1 /= 2
        }
        dn1 := 1
        for i := 0; i < len(primearray); i++ {
            if primearray[i]*primearray[i] > n1 {
                dn1 *= 2
                break
            }
            exponent := 1
            for n1%primearray[i] == 0 {
                exponent++
                n1 /= primearray[i]
            }
            if exponent > 1 {
                dn1 *= exponent
            }
            if n1 == 1 {
                break
            }
        }
        cnt = dn * dn1
        dn = dn1
    }
    return n * (n - 1) / 2
}

我得到:

原始版本:9.1690 100% Thaumkid的c版本:0.1060 8650% 首发版本:8.2520 111% 第二围棋版本:0.0230 39865%

我还尝试了Python3.6和pypy3.3-5.5-alpha:

原版本:8.629 100% Thaumkid的c版本:0.109 7916% python: 54.795 16% Pypy3.3-5.5-alpha: 13.291 65%

然后用下面的代码我得到:

原版本:8.629 100% Thaumkid的c版本:0.109 8650% Python3.6: 1.489 580% Pypy3.3-5.5-alpha: 0.582 1483%

def D(N):
    if N == 1: return 1
    sqrtN = int(N ** 0.5)
    nf = 1
    for d in range(2, sqrtN + 1):
        if N % d == 0:
            nf = nf + 1
    return 2 * nf - (1 if sqrtN**2 == N else 0)

L = 1000
Dt, n = 0, 0

while Dt <= L:
    t = n * (n + 1) // 2
    Dt = D(n/2)*D(n+1) if n%2 == 0 else D(n)*D((n+1)/2)
    n = n + 1

print (t)

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

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate <= n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index ++;
        triangle += index;
    }
    printf ("%ld\n", triangle);
}

gcc -lm -Ofast euler.c

时间。/ a.o ut

2.79s user 0.00s system 99% CPU 2.794 total

问题3:你能给我一些如何优化这些实现的提示吗 而不改变我确定因子的方法?任意优化 方法:更好、更快、更“地道”的语言。

C实现是次优的(正如Thomas M. DuBuisson所暗示的那样)，该版本使用64位整数(即长数据类型)。稍后我将研究程序集清单，但根据合理的猜测，在编译后的代码中进行了一些内存访问，这使得使用64位整数明显变慢。或者是生成的代码(比如在SSE寄存器中可以容纳更少的64位整数，或者将双精度整数舍入为64位整数更慢)。

下面是修改后的代码(简单地用int替换long，我显式内联factorCount，尽管我不认为这是gcc -O3所必需的):

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

static inline int factorCount(int n)
{
    double square = sqrt (n);
    int isquare = (int)square;
    int count = isquare == square ? -1 : 0;
    int candidate;
    for (candidate = 1; candidate <= isquare; candidate ++)
        if (0 == n % candidate) count += 2;
    return count;
}

int main ()
{
    int triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index++;
        triangle += index;
    }
    printf ("%d\n", triangle);
}

运行+计时它给出:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

作为参考，Thomas在前面的回答中给出了haskell实现:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

结论:ghc是一个很棒的编译器，但gcc通常会生成更快的代码。