只是为了好玩。下面是一个更“原生”的Haskell实现:

import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares

isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round

intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'

factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
  where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]

factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

使用ghc -O3，它在我的机器上持续运行0.55-0.58秒(1.73GHz Core i7)。

C版本中一个更有效的factorCount函数:

int factorCount (int n)
{
  int count = 1;
  int candidate,tmpCount;
  while (n % 2 == 0) {
    count++;
    n /= 2;
  }
    for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
    if (n % candidate == 0) {
      tmpCount = 1;
      do {
        tmpCount++;
        n /= candidate;
      } while (n % candidate == 0);
       count*=tmpCount;
      }
  if (n > 1)
    count *= 2;
  return count;
}

在main中使用gcc -O3 -lm将long类型更改为int类型，该程序始终在0.31-0.35秒内运行。

如果您利用第n个三角形数= n*(n+1)/2，并且n和(n+1)具有完全不同的质因数分解，则可以使两者运行得更快，因此可以将每个一半的因数数相乘，以得到整体的因数数。以下几点:

int main ()
{
  int triangle = 0,count1,count2 = 1;
  do {
    count1 = count2;
    count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
  } while (count1*count2 < 1001);
  printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}

将c代码的运行时间减少到0.17-0.19秒，它可以处理更大的搜索——大于10000个因数在我的机器上大约需要43秒。我给感兴趣的读者留下了类似的haskell加速。

Erlang实现存在一些问题。作为下面的基准，我测量的未修改的Erlang程序的执行时间为47.6秒，而C代码的执行时间为12.7秒。

(编辑:在Erlang/OTP版本24,2021年，Erlang有一个自动JIT编译器，旧的+本机编译器选项不再支持或需要。我保留下面这段文字作为历史文件。关于export_all的注释对于jit生成良好代码的能力仍然是有效的。)

The first thing you should do if you want to run computationally intensive Erlang code is to use native code. Compiling with erlc +native euler12 got the time down to 41.3 seconds. This is however a much lower speedup (just 15%) than expected from native compilation on this kind of code, and the problem is your use of -compile(export_all). This is useful for experimentation, but the fact that all functions are potentially reachable from the outside causes the native compiler to be very conservative. (The normal BEAM emulator is not that much affected.) Replacing this declaration with -export([solve/0]). gives a much better speedup: 31.5 seconds (almost 35% from the baseline).

但是代码本身有一个问题:对于factorCount循环中的每一次迭代，都要执行以下测试:

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;

C代码不这样做。一般来说，在相同代码的不同实现之间进行公平的比较是很棘手的，特别是如果算法是数值的，因为您需要确保它们实际上在做相同的事情。在某个实现中由于某个类型转换而产生的轻微舍入错误可能会导致它比另一个实现进行更多的迭代，即使两者最终得到相同的结果。

为了消除这个可能的错误源(并在每次迭代中摆脱额外的测试)，我重写了factorCount函数，如下所示，密切模仿C代码:

factorCount (N) ->
    Sqrt = math:sqrt (N),
    ISqrt = trunc(Sqrt),
    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
       true          -> factorCount (N, ISqrt, 1, 0)
    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
    case N rem Candidate of
        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
        _ -> factorCount (N, ISqrt, Candidate + 1, Count)
    end.

这个重写，没有export_all和本机编译，给了我以下运行时:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

这与C代码相比不算太糟:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

考虑到Erlang完全不适合编写数字代码，在这样的程序中只比C慢50%就已经很不错了。

最后，关于你的问题:

问题1:erlang、python和haskell是否会因为使用任意长度的整数而降低速度 只要值小于MAXINT，它们不就行了吗?

Yes, somewhat. In Erlang, there is no way of saying "use 32/64-bit arithmetic with wrap-around", so unless the compiler can prove some bounds on your integers (and it usually can't), it must check all computations to see if they can fit in a single tagged word or if it has to turn them into heap-allocated bignums. Even if no bignums are ever used in practice at runtime, these checks will have to be performed. On the other hand, that means you know that the algorithm will never fail because of an unexpected integer wraparound if you suddenly give it larger inputs than before.

问题4:我的函数实现是否允许LCO，从而避免在调用堆栈中添加不必要的帧?

是的，您的Erlang代码在最后调用优化方面是正确的。

#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

使用Haskell，您真的不需要显式地考虑递归。

factorCount number = foldr factorCount' 0 [1..isquare] -
                     (fromEnum $ square == fromIntegral isquare)
    where
      square = sqrt $ fromIntegral number
      isquare = floor square
      factorCount' candidate
        | number `rem` candidate == 0 = (2 +)
        | otherwise = id

triangles :: [Int]
triangles = scanl1 (+) [1,2..]

main = print . head $ dropWhile ((< 1001) . factorCount) triangles

在上面的代码中，我用普通的列表操作替换了@Thomas回答中的显式递归。代码仍然做着完全相同的事情，而不需要我们担心尾部递归。它运行(~ 7.49秒)比@Thomas回答的版本(~ 7.04秒)在我的机器上运行GHC 7.6.2，而来自@Raedwulf的C版本运行~ 3.15秒。GHC似乎在过去一年中有所改善。

PS:我知道这是一个老问题，我从谷歌搜索中偶然发现了它(我忘了我在搜索什么了，现在…)只是想评论一下关于LCO的问题，并表达我对Haskell的总体感受。我想对上面的答案进行注释，但是注释不允许代码块。

通过使用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

只是为了好玩。下面是一个更“原生”的Haskell实现:

import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares

isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round

intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'

factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
  where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]

factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

使用ghc -O3，它在我的机器上持续运行0.55-0.58秒(1.73GHz Core i7)。

C版本中一个更有效的factorCount函数:

int factorCount (int n)
{
  int count = 1;
  int candidate,tmpCount;
  while (n % 2 == 0) {
    count++;
    n /= 2;
  }
    for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
    if (n % candidate == 0) {
      tmpCount = 1;
      do {
        tmpCount++;
        n /= candidate;
      } while (n % candidate == 0);
       count*=tmpCount;
      }
  if (n > 1)
    count *= 2;
  return count;
}

在main中使用gcc -O3 -lm将long类型更改为int类型，该程序始终在0.31-0.35秒内运行。

如果您利用第n个三角形数= n*(n+1)/2，并且n和(n+1)具有完全不同的质因数分解，则可以使两者运行得更快，因此可以将每个一半的因数数相乘，以得到整体的因数数。以下几点:

int main ()
{
  int triangle = 0,count1,count2 = 1;
  do {
    count1 = count2;
    count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
  } while (count1*count2 < 1001);
  printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}

将c代码的运行时间减少到0.17-0.19秒，它可以处理更大的搜索——大于10000个因数在我的机器上大约需要43秒。我给感兴趣的读者留下了类似的haskell加速。