三角形数的除数(Euler 12)
本文关键字:Euler 三角形 | 更新日期: 2023-09-27 18:28:34
我发现了几个与这个问题相关的主题,我只想知道为什么我的代码返回不正确的数据。所以我们必须找到第一个除数超过500的三角形。详细信息可在此处找到:http://projecteuler.net/problem=12这是我的代码:
Int64 triangularnum = 1;
for (Int64 num = 2; num > 0; num++)
{
if(has501Divisors(triangularnum))
{
MessageBox.Show(triangularnum.ToString());
break;
}
triangularnum += num;
}
private bool has501Divisors(Int64 candidate)
{
bool has501 = false;
int count = 0;
for (int i = 1; i < Math.Sqrt(candidate); i++)
{
if (candidate % i == 0) count += 1;
if (count > 501)
{
return true;
}
}
return has501;
}
这给了我842161320号,这显然是不正确的。
您应该将count
编号增加2
而不是1
。
还有你的
if (count > 501)
部分不正确,因为您的边界应该是500
而不是501
。将其更改为count > 500
,而不是。
static void Main(string[] args)
{
Console.WriteLine(Find());
}
public static int Find()
{
int number = 0;
for (int i = 1; ; i++)
{
number += i; // number is triangle number i
if (CountDivisorsOfNumber(number) > 500)
return number;
}
}
private static int CountDivisorsOfNumber(int number)
{
int count = 0;
int end = (int)Math.Sqrt(number);
for (int i = 1; i < end; i++)
{
if (number % i == 0)
count += 2;
}
if (end * end == number) // Perfect square
count++;
return count;
}
这将打印76576500
,看起来是一个正确的解决方案。
问题是您将循环限制为平方根,这是明智的,但这意味着您需要将计数增加2,而不是增加1来计算两个除数。
将您的增量更改为:
if (candidate % i == 0) count += 2;
此外,您的计数检查会检查大于501的除数,而不是500。
快速查看,但您的检查不合格:
if (count > 501)
这将在计数502而不是501处停止。
for (int i = 1; i < Math.Sqrt(candidate); i++)
9可以被3整除,所以应该使用<=在这里另外,你除以1,你应该从i=2开始。