项目Euler问题12 - C ++ [英] Project Euler Problem 12 - C++

问题描述

我正在处理问题12关于第一个三角形数字与500除数。我试图强力解决方案。我在大约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）; 
} 
 
返回triangleNum; 
} 
 
 int NumOfDivisors（unsigned long long dividend）
 {
 int numDivisors = 0; 
设置< unsigned long long>除数; 
 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 ++; 
} 
 / *由于某种原因不检查上面的dups和
只是检查在集合中有多少项目在结束是慢
为（it = divisors.begin （）; it！= divisors.end（）; it ++）
 {
 numDivisors ++; 
} 
 * / 
} 
} 
 
 return numDivisors; 
} 
 
 int main（）
 {
 cout<< TriangleNumberDivisors（500）<< endl; 
 
 return 0; 
} 
  

更新：更改为只检查数字的平方根，并做了额外的检查，看看它是否是一个完美的正方形。这允许我完全删除集合。

您目前检查的除数​​最多为 dividend / 2

code>。你可以把它减少到 sqrt（dividend），这是渐近更快。如果 dividend 是正方形，则可能需要特殊情况。

我的问题12的C ++代码与您的相同，但使用此下限，并且只是计算除数而不是将其存储在集合中）需要大约1秒

I'm working on problem 12 regarding the first triangle number with 500 divisors. I tried to brute force the solution. I get 300 divisors in about 35 seconds and can't get 400 within 10 minutes. I'm going to alter my solution to use the prime factor method but I've seen now that people are still getting this solution with brute force in under a minute.

Can you please critique my code and tell me if I'm missing something that is making this horribly inefficient?

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

Update: Got it now, thanks. Changed to just check up to square root of the number, and did an additional check to see if it was a perfect square. This allowed me to remove the set entirely as well. 500 divisors ran in 12 seconds.

解决方案

You currently check for divisors up to dividend/2. You can reduce this to sqrt(dividend), which is asymptotically faster. A special case may be needed if dividend is square.

My C++ code for problem 12 (which does essentially the same as yours, but uses this lower limit, and also just counts divisors rather than storing them in the set) takes about 1 second

这篇关于项目Euler问题12 - C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！