C#三角数字优化

Question

任务是找到一个至少有500个除数的三角形数.

例如28有6个除数: 1,2,4,7,14,28

我的代码适用于多达200个除数,但对于500,它会永远运行...

有没有办法优化代码.比如我想过动态优化和memoization,但找不到办法呢？

            int sum = 0;
            int counter = 0;
            int count = 1;

            bool isTrue = true;
            while (isTrue)
            {
                counter = 0;
                sum += count;

                for (int j = 1; j <= sum; j++)
                {
                    if (sum % j == 0)
                    {
                        counter++;
                        if (counter == 500)
                        {
                            isTrue = false;
                            Console.WriteLine("Triangle number: {0}", sum);
                            break;
                        }
                    }
                }
                count++;
            }            
            Console.WriteLine("Number of divisors: {0}", counter);

Answer 1

忽略这个数字是三角形数字的事实.如果您可以快速解决此问题:

• 给定任意数n,确定它具有的除数

那么显然你可以快速解决欧拉#12.只需列出易于计算的三角形数字,确定每个的除数,并在得到500或更大的结果时停止.

那么如何快速确定除数的数量呢？正如你所发现的那样,当数字变大时,这是很多工作.

这是一个提示.假设你已经有了素数分解.让我们选择一个数字,比方说,196.将其分解为素数:

196 = 2 x 2 x 7 x 7

我只能通过看一下196有9个除数的因子分解来告诉你.怎么样？

因为196的任何除数是以下形式:

(1, 2 or 2x2) x (1, 7 or 7x7)

显然有九种可能的组合:

1 x 1
1 x 7
1 x 7 x 7
2 x 1
2 x 7
2 x 7 x 7
2 x 2 x 1
2 x 2 x 7
2 x 2 x 7 x 7

选择另一个号码.200,让我们说.那是2 x 2 x 2 x 5 x 5.所以有十二种可能性:

1 x 1
1 x 5
1 x 5 x 5
2 x 1
2 x 5
...
2 x 2 x 2 x 5 x 5

看模式？您采用素数分解,按素数对它们进行分组,并计算每组中的数量.然后,为每个数字添加一个并将它们相乘.再次,在200有3个三三两两2个的质数分解击掌.每个添加一个:四个和三个.将它们相乘:十二.这就是有多少除数.

因此,如果您知道素数分解,则可以非常快速地找到除数的数量.我们将除数问题减少到一个更容易的问题:你能弄清楚如何快速产生素数分解吗？