项目欧拉问题12 - C++

Question

我正在研究关于第一个具有500个除数的三角形数的问题12.我试图暴力破解解决方案.我在大约35秒内获得300个除数,并且在10分钟内无法获得400.我将改变我的解决方案以使用素因子方法,但我现在已经看到人们仍然在不到一分钟内用蛮力获得这个解决方案.

你能不能批评我的代码并告诉我,如果我错过了一些令这种可怕的低效率的东西？

unsigned long long TriangleNumberDivisors(int divisorTarget)
{
     unsigned long long triangleNum=1;
         unsigned long long currentNum=2;
     int numOfDivisors=0;


     numOfDivisors=NumOfDivisors(triangleNum);
     while(numOfDivisors<divisorTarget)
     {
         triangleNum+=currentNum;
         currentNum++;
         numOfDivisors=NumOfDivisors(triangleNum);
     }

     return triangleNum;
}

 int NumOfDivisors(unsigned long long dividend)
{
    int numDivisors=0;
    set<unsigned long long> divisors;
    set<unsigned long long>::iterator it;

    for(unsigned long long index=1; index<=dividend/2; index++)
    {
        if(dividend%index==0)
        {
            divisors.insert(index);
            numDivisors++;
            it=divisors.find(dividend/index);
            if(it==divisors.end())
            {
                divisors.insert(dividend/index);
                numDivisors++;
            }
              /*for some reason not checking for dups above and 
just checking for how many items are in the set at the end is slower
             for(it=divisors.begin();it!=divisors.end();it++)
             {
                   numDivisors++;
             }
                  */
        }
    }

    return numDivisors;
}

int main()
{
    cout<<TriangleNumberDivisors(500)<<endl;

    return 0;
}

更新:现在知道了,谢谢.改为只检查数字的平方根,并做了一个额外的检查,看看它是否是一个完美的正方形.这允许我完全删除该组.500秒的分数在12秒内完成.

Answer 1

您目前检查的是除数dividend/2.你可以将其减少到sqrt(dividend)渐近更快的速度.如果dividend是正方形,则可能需要特殊情况.

问题12的我的C++代码(它与你的基本相同,但是使用这个下限,并且只计算除数而不是将它们存储在集合中)大约需要1秒